#include <iostream>
#include <algorithm>
#include <list>
#include <vector>
#include <map>
using namespace std;
struct Money {
int value;
int count;
Money(int moneyValue, int moneyCount) {
value = moneyValue;
count = moneyCount;
}
};
void printUsedMoney(std::map<int, int> *usedMoney) {
for (std::map<int, int>::iterator i = usedMoney->begin(); i != usedMoney->end(); ++i)
{
cout << i->first << ":" << i->second << endl;
}
}
bool compareGreaterMoney(Money left, Money right) {
return (left.value) > (right.value);
}
void payMoney(int moneyUsedCount, std::vector<Money> *possMoney, std::map<int, int> *usedMoney) {
sort(possMoney->begin(), possMoney->end(), compareGreaterMoney);
int curUsed = moneyUsedCount;
for(std::vector<Money>::iterator i = possMoney->begin(); i != possMoney->end(); ++i) {
int needCount = curUsed/i->value;
if (curUsed%i->value > 0)
{
++needCount;
}
int usedCount = 0;
if (needCount > 0) {
if (needCount < i->count) {
usedCount = needCount;
i->count -= needCount;
}
else {
usedCount = i->count;
i->count = 0;
}
usedMoney->insert(pair<int, int>(i->value, usedCount));
curUsed -= (usedCount * i->value);
if (0 >= curUsed)
{
break;
}
}
}
if (curUsed <= 0) {
printUsedMoney(usedMoney);
}
else {
cout << "You don't have enough money. You need " << curUsed << " more."<< endl;
}
}
int main(){
int money = 0;
std:vector<Money> possMoney;
std::map<int, int> usedMoney;
while (cin >> money && money != 0){
possMoney.push_back(Money(1, 6));
possMoney.push_back(Money(2, 2));
possMoney.push_back(Money(5, 10));
possMoney.push_back(Money(10, 8));
possMoney.push_back(Money(20, 5));
possMoney.push_back(Money(50, 2));
possMoney.push_back(Money(100, 3));
payMoney(money, &possMoney, &usedMoney);
possMoney.clear();
usedMoney.clear();
}
}