Loading [MathJax]/jax/output/CommonHTML/jax.js

Задача F. Farming

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

Условие

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1t104

1u,v109

1x,y2105

1s,w109

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

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

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

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

Подзадача Баллы Дополнительные ограничения
tu,v,s,wx,y
1101t101u,v,s,w1001x,y100
2351t1031u,v,s,w1051x,y103
3551t1041u,v,s,w1091x,y105

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

В первом наборе данных вы забираете 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.055s 0.008s 13