Задача F. Farming

Автор:Денис Лысенко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Вы решили тряхнуть стариной и поиграть в вашу любимую игру 2000-ых годов - "Линейку". Одному вам было играть скучно и вы решили позвать с собой друга. Не найдя занятия лучше, вы с другом решили пофармить.

Ваш друг скаут нашёл t пар точек для фарма - Ai и Bi, таких, что на данный момент в точке Ai стоят xi мобов, а в точке Bi - yi. Дроп с каждого моба в точке Ai занимает si слотов инвентаря, а в точке Bi - wi. Также дроп с мобов для любой пары точек продаётся торговцу за одинаковую цену.

Вы придумали стратегию для фарма: вы со своим другом фармите поочередно каждую из t пар точек, до тех пор, пока не забьётся инвентарь, после чего вы сдаёте дроп и переходите к следующей паре точек. Вместимость вашего инвентаря - u слотов, а вашего друга v слотов.

Узнайте, максимальное количества дропа, которое вы можете вынести с каждой пары точек. Гарантируется, что суммарное количество дропа суммарно на всех парах точек не превосходит 106.

Формат входных данных

В первой строке подаётся единственное целое число t (1 ≤ t ≤ 104).

В первой строке каждого набора данных заданы два целых числа u и v (1 ≤ u,v ≤ 109) - количество слотов вашего инвентаря и вашего друга.

Во второй строке каждого набора данных заданы два целых числа x и y (1 ≤ x,y ≤ 2 ⋅ 105) - количество мобов на точках Ai и Bi.

В третьей строке каждого набора данных заданы два целых числа s и w (1 ≤ s,w ≤ 109) - количество слотов, который занимает дроп с точек Ai и Bi

Формат выходных данных

Для каждой пары точек выведите суммарное максимальное количества лута, который можно зафармить и унести со своим другом.

Ограничения

1 ≤ t ≤ 104

1 ≤ u,v ≤ 109

1 ≤ x,y ≤ 2 ⋅ 105

1 ≤ s,w ≤ 109

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения
tu,v,s,wx,y
1101 ≤ t ≤ 101 ≤ u,v,s,w ≤ 1001 ≤ x,y ≤ 100
2351 ≤ t ≤ 1031 ≤ u,v,s,w ≤ 1051 ≤ x,y ≤ 103
3551 ≤ t ≤ 1041 ≤ u,v,s,w ≤ 1091 ≤ x,y ≤ 105

Пояснение к примерам

В первом наборе данных вы забираете 3-х мобов с первого кэмпа и 3-х со второго, а ваш друг 3-х с первого и 2-х со второго. Итого 11 единиц лута.

Во втором наборе данных вы фармите всех мобов, 20 единиц лута.

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

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

Стандартный вход Стандартный выход
1
3
33 27
6 10
5 6
100 200
10 10
5 5
1 19
1 3
19 5
11
20
3

0.077s 0.014s 13