Rút tiền tối thiểu (Hit the Lottery)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cần biểu diễn số tiền nguyên dương $n$ bằng các tờ tiền mệnh giá $1,5,10,20,100$. Mỗi mệnh giá có số lượng không giới hạn. Hãy tìm số tờ ít nhất.

Input

Một dòng chứa $n$.

Output

In số tờ tiền ít nhất.

Subtask

Các giới hạn chung:

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

• Subtask 1 (20 điểm): $n \le 100$

• Subtask 2 (30 điểm): $n \le 10^5$

• Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Input

125

Output

3

Giải thích

$125=100+20+5$, cần $3$ tờ và không thể dùng chỉ $1$ hoặc $2$ tờ.