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