Леді напередрувала повну кишеню монет по 5, 10, 20 і 50 копійок, і коли вона має сплатити будь-яку суму, то вибирає свої монети таким чином, щоб використати мінімально можливу кількість монет.
Ваше завдання полягає у написанні програми, яка, враховуючи кількість монет по 5, 10, 20 і 50 копійок в кишені Леді, визначає кількість монет кожного номіналу та загальну кількість використаних монет так, що загальна кількість монет, яку вона може використати, була мінімальною. Зауважте, що Леді не завжди зможе заплатити потрібну суму грошей.
Перший рядок вхідного файлу містить п'ять цілих чисел – перші чотири це кількості відповідно 5, 10, 20 та 50 копійок, а п'яте число представляє суму, яку Леді має заплатити, в копійках. (Кількість монет кожного типу менша 1 000 000, а сума менша 100 000 000 копійок.)
У єдиному рядку вихідного файлу виведіть п'ять чисел: перші чотири – кількість монет кожного типу, які Леді має потратити, а також загальна кількість монет. Якщо розрахуватись Леді не може – виведіть .
Example 1
Example 2
Ця задача складається з п'яти підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі, а також всі тести всіх необхідних для неї підзадач. Необхідні підзадачі також вказані в таблиці.
№ підзадачі | Бали | Обмеження | Примітка |
0 | 0 | Тести з умови | |
1 | 17 | У Леді немає двох різних монет (монет різного номіналу), тобто лише одне з перших чотирьох чисел у вхідному файлі може бути ненульовим. | |
2 | 19 | Кількість монет кожного виду не більше 100. | |
3 | 21 | У Леді немає монет номіналом в 50 копійок. | |
4 | 43 | Обмеження з умови (кількості до 10^6, потрібно зібрати до 10^6). | Необхідні підзадачі: 0, 1, 2, 3. |