该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Allen 有很多钱。他的银行账户中有 n 美元。出于安全原因，他想将这些钱提取出来。（我们这里不会透露原因）美元钞票的面额为 1，5，10，20，100 美元。请问 Allen 提取出全部余额后，最少需要多少张钞票？

输入

输入包含一个整数 n $(1 \leq n \leq 10^9)$，表示 Allen 的银行账户余额。

输出

输出最少需要的钞票数。

示例

输入 1：

125

输出 1：

3

输入 2：

43

输出 2：

5

输入 3：

1000000000

输出 3：

10000000

说明

在第一个例子中，Allen 可以使用一张100美元钞票，一张20美元钞票和一张5美元钞票来提取125美元。没有办法用一或两张钞票提取125美元。

在第二个例子中，Allen 可以使用两张20美元钞票和三张1美元钞票来提取43美元。

在第三个例子中，Allen 可以使用一千万张100美元钞票来提取1000000000美元。