题目描述

你正在为新一代智能。售货机设计找零系统。售货机支持的硬币面值为{1, 5, 10, 50, 100, 500}单位。当顾客购买商品后，系统需要找零n单位货币，目标是使用最少数量的硬币完成找零。 给定找零金额n（0 ≤ n ≤ 10000），计算最少需要的硬币数量。

输入格式

输入一个找零金额n（0 ≤ n ≤ 10000）；

输出格式

硬币数量

输入/输出样例

63

5

样例解释

需要找零63单位：

• 1枚50单位硬币（剩余13）
• 1枚10单位硬币（剩余3）
• 3枚1单位硬币 共1+1+3=5枚硬币。