Автор: | Денис Лысенко | Ограничение времени: | 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
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | ||
---|---|---|---|---|
t | u,v,s,w | x,y | ||
1 | 10 | 1 ≤ t ≤ 10 | 1 ≤ u,v,s,w ≤ 100 | 1 ≤ x,y ≤ 100 |
2 | 35 | 1 ≤ t ≤ 103 | 1 ≤ u,v,s,w ≤ 105 | 1 ≤ x,y ≤ 103 |
3 | 55 | 1 ≤ t ≤ 104 | 1 ≤ u,v,s,w ≤ 109 | 1 ≤ x,y ≤ 105 |
В первом наборе данных вы забираете 3-х мобов с первого кэмпа и 3-х со второго, а ваш друг 3-х с первого и 2-х со второго. Итого 11 единиц лута.
Во втором наборе данных вы фармите всех мобов, 20 единиц лута.
В третьем наборе в ваш инвентарь ничего не поместится, а вот напарник может забрать лут с трёх мобов на второй точке. Ответ 3.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|