Hit the Lottery

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Represent a positive amount $n$ using unlimited banknotes of denominations $1,5,10,20,100$. Find the minimum number of banknotes.

Input

One line contains $n$.

Output

Print the minimum number of banknotes.

Subtasks

General constraints:

• $1 \le n \le 10^9$.

• Subtask 1 (20 points): $n \le 100$

• Subtask 2 (30 points): $n \le 10^5$

• Subtask 3 (50 points): No additional constraints.

Examples

Input

125

Output

3

Explanation

$125=100+20+5$, so three banknotes are sufficient, and one or two banknotes cannot total $125$.