Задача F. Farming ≡

Условие

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

Ваш друг скаут нашёл t пар точек для фарма - A_i и B_i, таких, что на данный момент в точке A_i стоят x_i мобов, а в точке B_i - y_i. Дроп с каждого моба в точке A_i занимает s_i слотов инвентаря, а в точке B_i - w_i. Также дроп с мобов для любой пары точек продаётся торговцу за одинаковую цену.

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ t ≤ 10⁴

1 ≤ u,v ≤ 10⁹

1 ≤ x,y ≤ 2 ⋅ 10⁵

1 ≤ s,w ≤ 10⁹

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

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

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

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

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

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

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

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

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

3
33 27
6 10
5 6
100 200
10 10
5 5
1 19
1 3
19 5

11
20
3