Скриня зі скарбами зомбі#3085
У загублене село прибули хоробрі воїни. Їм дуже пощастило знайти багато скарбів і велику скриню для цих скарбів, але вони також зустріли злих зомбі.
Воїни були такими хоробрими, що вирішили перемогти зомбі й забрати всі скарби. Після довгої й виснажливої битви, що тривала від ранку до ночі, воїни зрозуміли, що зомбі — це нежить, і їх неможливо перемогти.
Звісно, скарби не можна тут залишати. На жаль, воїни не можуть забрати всі скарби, оскільки об'єм скрині обмежено. Існує тільки два типи скарбів: смарагди та сапфіри. Всі смарагди однакові за розміром і вартістю, причому їх кількість необмежена. Те саме стосується і сапфірів.
Ви є жерцем воїнів, що має чарівний артефакт — комп'ютер, і знаючи місткість скрині, а також розмір і вартість кожного типу коштовних каменів, ви повинні обчислити максимальну вартість скарбів, яку воїни зможуть понести зі скринею.
Перший рядок містить кількість тестових випадків (t \leq 200). Кожен тестовий випадок задається в окремому рядку й містить п'ять цілих чисел: , s_1, v_1, s_2, v_2, де — місткість скрині, s_1 і v_1 — розмір і вартість смарагду; s_2 і v_2 — розмір і вартість сапфіру. Всі значення — додатні цілі числа, що містяться в -бітному знаковому цілому числі.
Для кожного тестового випадку виведіть в окремому рядку максимальну вартість скарбів, які можна забрати у скрині.
Приклад 1