Cashier Mitu at the campus canteen only stocks coins of a few fixed denominations, in unlimited supply, and wants to give change using the FEWEST coins possible for any amount. You have coins of denominations 1, 5, 10, 25 (unlimited supply of each). Given an amount N, print the MINIMUM number of coins needed to make exactly N.
Input
One integer N.
Output
Minimum coin count.
Constraints
1 ≤ N ≤ 10^6
Sample Input
30
Sample Output
2
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.