Бусинки
У мене є декілька (скажімо, n), бусинок (маленькі сткяні кульки), і я збираюсь купити декілька коробок для їх збереження. Коробки бувають двох типів:
Тип 1: кожна коробка вартістю c_1 може містити рівно n_1 бусинок.
Тип 2: кожна коробка вартістю c_2 може містити рівно n_2 бусинок.
Я хочу, щоб кожна з використаних коробок була заповнена з врахуванням її місткості, а також звести до мінімуму сукупну вартість їх придбання. Так як дана задача занадто важка для мене, і щоб вияснити, як розподілити мої бусинки по коробкам, я прошу вашої допомоги. Я хочу, щоб ваша програма також була ефективною.
Вхідні дані
Вхідний файл може містити декілька тестів. Кожен тестовий приклад починається з рядка, який містить ціле число n (1 ≤ n ≤ 2000000000). Другий рядок містить c_1 та n_1, а третій рядок містить c_2 та n_2. Тут c_1, c_2, n_1 та n_2 - усі натуральні числа, які мають значення менші за 2000000000.
Тест, який містить нуль для n у першому рядку, завершує вхідні дані.
Вихідні дані
Для кожного вхідного тесту вивести рядок, який містить мінімальний розв'язок: вартість (два невід'ємних цілих числа m_1 та m_2, де m_i = число рівне типу i-тої коробки), якщо така існує, або вивести " failed" у протилежному випадку.
Якщо розв'язок існує, то можна вважати, що він унікальний.