Скриня зі скарбами зомбі
Кілька хоробрих воїнів прибули до загубленого села. Їм дуже пощастило, адже вони знайшли там безліч скарбів, а також велику скриню, в якій, окрім цінностей, ховалися сердиті зомбі.
Воїни були настільки відважними, що вирішили здолати зомбі, щоб потім забрати всі скарби. Жорстокий і затяжний бій тривав з ранку до ночі, після чого воїни зрозуміли, що зомбі є нежиттю і їх неможливо перемогти.
Звісно, скарби не повинні залишатися тут. На жаль, воїни не можуть винести всі скарби через обмежені розміри скрині. Існують лише два типи скарбів: смарагдові та сапфірові. Усі смарагди мають однаковий розмір і вартість, і їх нескінченна кількість. Те ж саме стосується сапфірів.
Ви, як священик воїнів з чарівним артефактом — комп'ютером, знаючи розмір скрині, вартість і розмір кожного типу каменю, повинні обчислити максимальну вартість скарбів, які наші воїни зможуть забрати.
Вхідні дані
Перший рядок містить кількість тестів t (t ≤ 200). Кожен тест в окремому рядку містить п'ять цілих чисел n, s[1], v[1], s[2], v[2], що вказують на розмір скрині n, а також розмір і вартість смарагда s[1] і v[1], і сапфіра s[2], v[2]. Усі числа є натуральними і вміщуються в 32-біта.
Вихідні дані
Для кожного тесту виведіть в окремому рядку номер тесту і найбільшу вартість скарбів, яку можна винести за допомогою скрині.