Making Change

Interview

Time limit1sMemory limit1024 MB

Summary

Given a purchase price P in cents, output the fewest 25, 10, 5, and 1 cent coins that make change for one dollar.

Level: Easy2 of 10
Topics: Greedy, Math
Solved: No attempts yet

Problem

Given the amount of a purchase $P$ in cents, where $1 \le P \le 99$ , determine how to make change for a dollar. Use the four standard US coin denominations: 1, 5, 10, and 25 cents. The way to make change uses the fewest coins.

Input

A single line with one integer $P$ , the amount of the purchase.

Output

A single line with four integers: the number of 25 cent, 10 cent, 5 cent, and 1 cent coins to give as change, in that order.

Examples1

Example 1
Input
```
43
```
Expected output
```
2 0 1 2
```