Ngân hàng có các mệnh giá 1, 2, 5, 10, 20, 50, 100, 200, 500 nghìn đồng, mỗi loại có không giới hạn số tờ. Cần đổi N nghìn đồng ra ít tờ tiền nhất. Hỏi cần bao nhiêu tờ?
Minh họa đổi 67 nghìn đồng
Dữ liệu vào
Một số nguyên N.
Kết quả
Số tờ ít nhất.
Giới hạn
1 ≤ N ≤ 10^18.
Ví dụ 1 – vào
67
Ví dụ 1 – ra
4
Ví dụ 2 – vào
3
Ví dụ 2 – ra
2