Задача: Автомат по продаже билетов

В Московском метрополитене вновь появляются автоматы для продажи билетов. Вас просят написать программу, которая будет рассчитывать, какую сдачу и какими купюрами и монетами требуется выдать пассажиру.

Входные данные
Вводится сначала стоимость билета, который хочет приобрести пассажир, затем общее количество купюр и монет, которые он опустил в автомат, а затем достоинства каждой из этих купюр и монет. Входные данные записаны в одной строке и разделены пробелами. Известно, что сумма всех купюр больше, чем стоимость билета. Во всех тестовых примерах стоимость билета – натуральное число, не превосходящее 1 000 рублей, количество купюр и монет не более 50, достоинство каждой не превосходит 500 рублей. Общая сумма денег, опущенных в автомат покупателем, превосходит стоимость билета.

Выходные данные
Программа должна вычислить, какими купюрами и монетами можно выдать сдачу, и вывести достоинство каждой из этих купюр или монет в произвольном порядке. Автомат может выдавать сдачу купюрами в 10, 50, 100 и 500 рублей, а также монетами в 1, 2 и 5 рублей. Если решений несколько, требуется выдать одно любое из них. Если решений нет, требуется выдать текст:

Sorry! Our monetary system is not perfect!
Please, choose another way to pay!
Thank you!

Примеры

Ваш ответ: