Задача B. Тонкий и толстый ≡

Условие

На финал чемпионата мира по программированию отправилось так много болельщиков (P человек), что для них пришлось организовать чартерные рейсы. Авиакомпания, доставляющая болельщиков, имеет в своем распоряжении N самолетов. По политическим соображениям, авиакомпания должна использовать для доставки пассажиров все имеющиеся самолёты.

Каждый самолет имеет две модификации. В модификации "Тонкий" самолет может поднять любое количество пассажиров в отрезке [a₁, b₁]. Перевозить меньше a₁ пассажиров экономически невыгодно, а больше b₁ пассажиров самолет просто не сможет поднять. В модификации "Толстый" самолет может поднять любое количество пассажиров в отрезке [a₂, b₂].

Требуется определить, можно ли распределить P болельщиков по N самолетам так, что все самолеты взлетят и их использование будет экономически выгодным. Каждый самолет может быть использован только в одном рейсе и в одной из модификаций.

Рекомендуется рассмотреть частичные решения

N ≤ 1000

Формат входного файла

Во входном файле находятся целые числа N P a₁ b₁ a₂ b₂.

Формат выходного файла

Если требуемая рассадка пассажиров существует, выведите два целых неотрицательных числа, дающие в сумме N: необходимое количество самолетов "тонкой" и "толстой" модификаций. Если существует несколько решений, выведите то, в котором количество самолетов "тонкой" модификации максимально. Если решения не существует, выведите два нуля через пробел.

Ограничения

1 ≤ N, P ≤ 10⁹

1 ≤ a₁ ≤ b₁ < a₂ ≤ b₂ ≤ 10⁹

Примеры тестов

10 50 2 4 7 10

8 2

10 200 2 4 7 10

0 0

Разбор

Обозначим за x количество "Толстых" самолетов. Тогда количество "Тонких" самолетов будет равно N − x. На x накладывается естественное ограничение 0 ≤ x ≤ N.

Минимальное количество человек, которое можно разместить в самолетах при фиксированном x составляет a₁(N − x) + a₂ x. Аналогично, максимальное количество составляет b₁(N − x) + b₂ x. Любое количество пассажиров между максимальным и минимальным легко можно расположить в самолетах следующим образом: сначала наполнить все самолеты минимальным количеством пассажиров a₁(N − x) + a₂ x, а затем добавлять их в первый самолет, пока он не заполнится, затем во второй и т.д.

Таким образом, чтобы при фиксированном x в самолетах разместить P человек, необходимо и достаточно, чтобы выполнялось условие

a₁(N − x) + a₂ x ≤ P ≤ b₁(N − x) + b₂ x.

Если изменять x в допустимых пределах от 0 до N, получаем ограничение на x:

P − a₁ Na₂ − a₁ ≤ x ≤ P − b₁ Nb₂ − b₁

Учтем и естественные ограничения на x. Тогда x должен удовлетворять условию L ≤ x ≤ R, где

L = max(0, P − a₁ Na₂ − a₁), R = min(N, P − b₁ Nb₂ − b₁)

По условию задачи нужно максимизировать количество самолетов "тонкой" модификации, то есть, минимизировать x. Значит, в качестве x нужно взять ближайшее справа к L целое число. Если это число превосходит R, тогда следует вывести в выходной файл "0 0".

Отметим, что задача может быть решена в целых числах, поскольку для округления дроби к ближайшему целому справа можно использовать целочисленное деление с прибавлением единицы, если числитель не делится нацело на знаменатель.

Отметим, что при вычислении числителя и знаменателя в приведенных выше формулах может возникнуть переполнение 32-разрядных целых чисел (с учетом ограничения 10⁹ на все величины), поэтому следует использовать 64-разрядные целые числа.