Сундук с сокровищами зомби
Сундук с сокровищами зомби
Несколько храбрых воинов пришли к потерянной деревне. Им очень повезло, потому что там они нашли очень много сокровищ, а также большой сундук в котором кроме ценностей находились сердитые зомби.
Воины были настолько смелыми, что они решили победить зомби, после чего забрать все сокровища. Жестокий и затянувшийся бой длился с утра до ночи, после чего воины поняли что зомби являются нежитью и непобедимы.
Конечно, сокровища не должны оставаться здесь. К сожалению, воины не смогут унести все сокровища из-за ограниченных размеров сундука. Имеются только два типа сокровищ: изумрудные и сапфировые. Все изумруды равны по размеру и стоимости, их бесконечное количество. То же можно сказать и о сапфирах.
Будучи священником воинов с волшебным артефактом - компьютером, и зная размер сундука, стоимость и размер каждого типа камня, Вам следует вычислить максимальную стоимость сокровищ, которые наши воины смогут забрать.
Входные данные
Первая строка содержит количество тестов t (t ≤ 200). Каждый тест в отдельной строке содержит пять целых чисел n, s1
, v1
, s2
, v2
, указывающих на размер сундука n, а также размер и стоимость изумруда s1
и v1
, и сапфира s2
, v2
. Все числа являются натуральными и помещаются в 32-бита.
Выходные данные
Для каждого теста вывести в отдельной строке номер теста и наибольшую стоимость сокровищ, которую удастся вынести при помощи сундука.
2 100 1 1 2 2 100 34 34 5 3
Case #1: 100 Case #2: 86