Một điểm rút tiền ATM có các lại tiền giá lần lượt như sau: 10.000 đồng, 20.000 đồng, 50.000 đồng, 100.000 đồng, 200.000 đồng và 500.000 đồng (mỗi loại có số lượng không giới hạn). Một khách hàng cần rút ra một số tiền M đồng (Giả sử rằng sau khi đã kiểm tra đầy đủ các thông số về bảo mật cá nhân). M là bội số của 10000. Hãy tìm cách trả sao cho khách hàng nhận được số lượng tờ tiền là ít nhất.

Input: nhập từ bàn phím gồm một số nguyên dương là số tiền cần rút, không quá 1 tỉ đồng.

Ghi ra màn hình: số lượng tờ tiền ít nhất phải trả

Ví dụ:

Input

9870000

Output

23

Giải thích:

1 tờ 20K, 1 tờ 50K, 1 tờ 100K, 1 tờ 200K, 19 tờ 500K.