问题陈述

高桥王国使用的硬币包括1!日元硬币、2!日元硬币，以此类推，直到10!日元硬币。其中，$N! = 1 \\times 2 \\times \\dots \\times N$。

高桥拥有每种硬币100个，他打算用不找零的方式购买价值为 $P$ 日元的产品。

我们可以证明总有一种方式可以实现支付。

他至少需要使用多少硬币来付款？

约束条件

• $1 \\leq P \\leq 10^7$
• $P$ 是一个整数。

输入

输入格式如下，从标准输入中获取：

$P$

输出

打印所需的最少硬币数量。

示例输入 1

9

示例输出 1

3

通过使用一枚1!日元硬币、一枚2!日元硬币和一枚3!日元硬币，我们可以准确支付价值为9日元的产品。没有比这更少硬币的支付方式。

示例输入 2

119

示例输出 2

10

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

示例输入 3

10000000

示例输出 3

24