题目描述

你拥有无限多枚硬币，硬币的面值分别为 $1$、$5$、$10$、$20$、$50$、$100$。给定一个数额 $w$，请你计算最少需要使用多少枚硬币才能恰好凑出 $w$。

输入格式

一行一个正整数 $w$，表示需要凑出的数额。

输出格式

一行一个整数，表示凑出 $w$ 所需的最少硬币枚数。

样例

6

2

提示

使用 $1$ 枚面值为 $5$ 的硬币和 $1$ 枚面值为 $1$ 的硬币，共 $2$ 枚即可凑出 $6$。

数据范围

• 对于 $100\%$ 的数据，保证 $1 \le w \le 10^9$。
• 题目保证 $w$ 一定有解。