Hit the Lottery codeforces in c++

 A. Hit the Lottery

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Allen has a LOT of money. He has n$n$ dollars in the bank. For security reasons, hwants to withdraw it in cash (we will not disclose the reasons here). The denominations for dollar bills are 

1$1$, 5$5$, 10$10$, 20$20$, 100$100$. What is the minimum number of bills Allen could receive after withdrawing his entire balance?

Input

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

Output

Output the minimum number of bills that Allen could receive.

Examples

input

Copy

125

output

Copy

3

input

Copy

43

output

Copy

5

input

Copy

1000000000

output

Copy

10000000

Note

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

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

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

---------------------------------------------------------------------------------------------------------------

solution:

---------------------------------------------------------------------------------------------------------------

Copy

#include<iostream>
using namespace std;

int main()
{
	int amount, note100, note20, note10, note5, note1;
	note100 = note20 = note10 = note5 = note1 = 0;
	cin >> amount;
	if (amount >= 100)
	{
		note100 = amount / 100;
		amount -= note100 * 100;
	}
	if (amount >= 20)
	{
		note20 = amount / 20;
		amount -= note20 * 20;
	}
	if (amount >= 10)
	{
		note10 = amount / 10;
		amount -= note10 * 10;
	}
	if (amount >= 5)
	{
		note5 = amount / 5;
		amount -= note5 * 5;
	}
	if (amount >= 1)
	{
		note1 = amount;
	}

	cout << (note100 + note20 + note10 + note5 + note1) << endl;

	return 0;
}