Несколько храбрых воинов пришли к потерянной деревне. Им очень повезло, потому что там они нашли очень много сокровищ, а также большой сундук в котором кроме ценностей находились сердитые зомби.

Воины были настолько смелыми, что они решили победить зомби, после чего забрать все сокровища. Жестокий и затянувшийся бой длился с утра до ночи, после чего воины поняли что зомби являются нежитью и непобедимы.

Конечно, сокровища не должны оставаться здесь. К сожалению, воины не смогут унести все сокровища из-за ограниченных размеров сундука. Имеются только два типа сокровищ: изумрудные и сапфировые. Все изумруды равны по размеру и стоимости, их бесконечное количество. То же можно сказать и о сапфирах.

Будучи священником воинов с волшебным артефактом - компьютером, и зная размер сундука, стоимость и размер каждого типа камня, Вам следует вычислить максимальную стоимость сокровищ, которые наши воины смогут забрать.

Входные данные

Первая строка содержит количество тестов t (t ≤ 200). Каждый тест в отдельной строке содержит пять целых чисел n, s1, v1, s2, v2, указывающих на размер сундука n, а также размер и стоимость изумруда s1 и v1, и сапфира s2, v2. Все числа являются натуральными и помещаются в 32-бита.

Выходные данные

Для каждого теста вывести в отдельной строке номер теста и наибольшую стоимость сокровищ, которую удастся вынести при помощи сундука.