Minimize Cash Dispense Bills

You are required to create a program that, given an amount of money, determines the minimum number of bills needed to dispense that amount using the following denominations: \(100, 50, 20, 10, 5,\) and \(1\).

Your program should continuously read input amounts from stdin until the number 0 is encountered. For each non-zero amount, output a line in the exact format:

100s: X, 50s: Y, 20s: Z, 10s: A, 5s: B, 1s: C

where X, Y, Z, A, B, and C correspond to the number of bills of \(100, 50, 20, 10, 5,\) and \(1\) respectively. The goal is to minimize the total number of bills dispensed.

Example:

• Input: 376
• Output: 100s: 3, 50s: 1, 20s: 1, 10s: 0, 5s: 1, 1s: 1

inputFormat

The input consists of several lines. Each line contains a single integer representing the amount of money. The input terminates with a line containing a single zero (0), which should not be processed.

outputFormat

For each input amount (except the terminating 0), output one line with the format:

100s: X, 50s: Y, 20s: Z, 10s: A, 5s: B, 1s: C

where X, Y, Z, A, B, and C denote the number of \(100, 50, 20, 10, 5,\) and \(1\) bills respectively such that the total count of bills is minimized.

## sample

376
123
6879
0

100s: 3, 50s: 1, 20s: 1, 10s: 0, 5s: 1, 1s: 1
100s: 1, 50s: 0, 20s: 1, 10s: 0, 5s: 0, 1s: 3
100s: 68, 50s: 1, 20s: 1, 10s: 0, 5s: 1, 1s: 4

</p>