Challenge: Fewest Notes

Lab Python Beginner 10 points

Using Indian notes and coins of 2000, 500, 200, 100, 50, 20, 10, 5, 2 and 1 rupees, pay an amount with the fewest pieces (greedy works for these values). Print each value used with its count, biggest first, as <value> x <count>, then Total pieces: <n>.

Input

One whole number (1 ≤ amount ≤ 100000).

Output

As described.

Example

Input

Output

2000 x 1
500 x 1
200 x 1
50 x 1
20 x 1
10 x 1
5 x 1
2 x 1
1 x 1
Total pieces: 9

Sample input available Sample output available

Editor

Python

Hints

Go from the biggest value to the smallest.

amount // v is how many of that value fit.

Solution explanation

For this set of values, taking the biggest possible piece first is always optimal.

Show solution

amount = int(input())
total = 0
for v in [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]:
    if amount >= v:
        k = amount // v
        amount -= k * v
        total += k
        print(v, "x", k)
print("Total pieces:", total)

Output

Answer