Hit the Lottery

Description:

Input:

The first and only line of input contains a single integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

Output:

Output the minimum number of bills that Allen could receive.

Sample Input:

125

Sample Output:

3

Sample Input:

43

Sample Output:

5

Sample Input:

1000000000

Sample Output:

10000000

Note:

In the first sample case, Allen can withdraw this with a $$$100$$$ dollar bill, a $$$20$$$ dollar bill, and a $$$5$$$ dollar bill. There is no way for Allen to receive $$$125$$$ dollars in one or two bills.

In the second sample case, Allen can withdraw two $$$20$$$ dollar bills and three $$$1$$$ dollar bills.

In the third sample case, Allen can withdraw $$$100000000$$$ (ten million!) $$$100$$$ dollar bills.