Бусинки
У меня есть несколько (скажем, 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" в противном случае.
Если решение существует, то можно считать, что оно уникально.