Задача ATM
Правда, вам набридли абсолютно неприродні олімпіадні задачі? Ну навіщо казати: «Якби банкомат заправили банкнотами по 10, 50 і 60 рублів, то суму 120 варто було б видавати не як 100+10+10, а як 60+60…» Ніхто ж не стане вводити в обіг банкноти номіналом 60… Тому зараз пропонуємо розв’язати абсолютно практичну задачу.
В обігу перебувають банкноти номіналами 1, 2, 5, 10, 20, 50, 100, 200 та 500 гривень. Причому, банкноти номіналами 1 грн та 2 грн в банкомати ніколи не кладуть. Так що в банкоматі є N5 штук банкнот по 5 грн, N10 штук банкнот по 10 грн, N20 штук банкнот по 20 грн, N50 штук банкнот по 50 грн, N100 штук банкнот по 100 грн, N200 штук банкнот по 200 грн та N500 штук банкнот по 500 грн. Для банкомата діють адміністративне обмеження «видавати не більш як 2000 грн за один раз» та технічне обмеження «видавати не більш як 40 банкнот за один раз». В останньому обмеженні мова йде про сумарну кількість банкнот (можливо, різних номіналів).
Напишіть програму, яка визначатиме, як видати потрібну суму мінімально можливою кількістю банкнот (з урахуванням указаних обмежень).
Технічні умови.
Програма ATM читає з пристрою стандартного введення (клавіатури) спочатку кількості банкнот N5, N10, N20, N50, N100, N200 та N500, потім суму S, яку треба видати. Усі числа вхідних даних є цілими, перебувають в межах від 0 включно до 5000 включно.
Програма повинна вивести на пристрій стандартного виведення(екран) сім чисел — скільки треба видати банкнот по 5 грн, по 10 грн, по 20 грн, по 50 грн, по 100 грн, по 200 грн та по 500 грн. Ці сім чисел треба вивести в один рядок, розділяючи пропусками. Сума цих чисел (загальна кількість банкнот до видачі) повинна бути мінімально можливою. Якщо видати суму, дотримуючись обмежень, неможливо, програма повинна замість відповіді вивести -1.
Приклади
Введення
0 100 1 100 0 0 0 190
Виведення
0 2 1 3 0 0 0
Введення
5000 2000 5000 2000 5000 2000 500 17
Виведення
-1