GRAND ASSIGNMENT - 1 Denominations

 Denominations

Given an amount, write a program to find a minimum number of currency notes of different denominations that sum to the given amount. Available note denominations are 1000, 500, 100, 50, 20, 5, 1.

---

Input

The input contains single integer N.

---

Output

The first line of output should contain the number of 1000 notes, print "1000:a"
The second line of output should contain the number of 500 notes, print "500:b"
The third line of output should contain the number of 100 notes, print "100:c".
The fourth line of output should contain the number of 50 notes, print "50:d".
The fifth line of output should contain the number of 20 notes., print "20:e".
The sixth line of output should contain the number of 5 notes, print "5:f".
The seventh line of output should contain the number of 1 notes, print "1:g".
In place of (a, b, c, d, e, f, g), print the count of corresponding notes.

---

Explanation

For example, if the given amount is 8593, in this problem you have to give the minimum number of notes that sum up to the given amount. Since we only have notes with denomination 1000, 500, 100, 50, 20, 5 and 1, we can only use these notes.

Number of 1000 notes => 1000 x 8 = 8000  
Number of 500 notes  =>  500 x 1 =  500  
Number of 100 notes  =>  100 x 0 =    0  
Number of 50 notes   =>   50 x 1 =   50  
Number of 20 notes   =>   20 x 2 =   40  
Number of 5 notes    =>    5 x 0 =    0  
Number of 1 notes    =>    1 x 3 =    3  
----------------------------------------  
Total                =>            8593  
----------------------------------------

So the output should be

1000:8
500:1
100:0 
50:1 
20:2
5:0
1:3

Sample Input 1

8593

Sample Output 1

1000:8
500:1
100:0
50:1
20:2
5:0
1:3

Sample Input 2

4

Sample Output 2

1000:0
500:0
100:0
50:0
20:0
5:0
1:4

nominals=(1000,500,100,50,20,5,1)

amount=int(input())

output={}

for n in nominals :

    output[n]=amount//n 

    amount%=n 

for k,v in output.items():

    print(k,v,sep=":")