阶乘日元硬币

题目描述

高桥王国使用的硬币面额为 $1!$ 日元、$2!$ 日元、$\dots$、$10!$ 日元。这里，$N! = 1 \times 2 \times \dots \times N$。

高桥每种硬币各有 $100$ 枚。他打算购买一件价值 $P$ 日元的商品，并且恰好支付金额、不找零。

可以证明总存在这样的支付方式。

他至少需要使用多少枚硬币？

输入格式

输入按以下格式从标准输入给出：

$P$

输出格式

输出所需硬币的最少枚数。

样例

9

3

用一枚 $(1! =) 1$ 日元硬币、一枚 $(2! =) 2$ 日元硬币和一枚 $(3! =) 6$ 日元硬币，恰好可以支付价值 $9$ 日元的商品。无法用更少的硬币支付这个金额。

119

10

应使用一枚 $1!$ 日元硬币、两枚 $2!$ 日元硬币、三枚 $3!$ 日元硬币和四枚 $4!$ 日元硬币。

10000000

24

数据范围

• $1 \le P \le 10^7$
• $P$ 为整数