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