题目描述

小 D 在游乐园中发现了一台纪念币自动售货机，一枚纪念币的价格为 $P$ 美分。

售货机只接受以下四种硬币：

• $1$ 美元硬币，面值为 $100$ 美分；
• $25$ 美分硬币；
• $10$ 美分硬币；
• $1$ 美分硬币。

售货机不会找零，因此小 D 必须恰好投入 $P$ 美分。为了尽快完成投币，他希望使用的硬币数量尽可能少。

假设小 D 拥有足够多的各种硬币，请计算他最少需要投入多少枚硬币。

输入格式

输入一行，包含一个正整数 $P$，表示纪念币的价格，单位为美分。

输出格式

输出一个整数，表示恰好支付 $P$ 美分所需的最少硬币数量。

样例

14

5

21

3

30

3

样例解释

样例 1 中，使用 $1$ 枚 $10$ 美分和 $4$ 枚 $1$ 美分，共 $5$ 枚硬币。

样例 2 中，使用 $2$ 枚 $10$ 美分和 $1$ 枚 $1$ 美分，共 $3$ 枚硬币。

样例 3 中，使用 $3$ 枚 $10$ 美分，共 $3$ 枚硬币。如果先用 $1$ 枚 $25$ 美分再补 $5$ 枚 $1$ 美分，则需要 $6$ 枚，不是最优。

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le P \le 10^9$。