A long time ago, ticket prices were:
1 trip — 15 rubles,
5 trips — 70 rubles,
10 trips — 125 rubles,
20 trips — 230 rubles,
60 trips — 440 rubles.
The passenger plans to make n trips. Determine how many tickets of each type he must purchase so that the total number of paid trips is not less than n, and the total cost of purchased tickets — minimal.
Input: The program receives one number n as input.
Output: The program should output five integers: the number of tickets for 1, 5, 10, 20, 60 trips to be purchased. If for some given n there are several ways to purchase tickets of the same total cost, you need to print the combination of tickets that gives more trips.
Examples
| # |
Input |
Output |
| 1 |
1 |
1 0 0 0 0 |
| 2 |
7 |
2 1 0 0 0 |