eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сундук с сокровищами зомби

Сундук с сокровищами зомби

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

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

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

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

Первая строка содержит количество тестов t (t200). Каждый тест в отдельной строке содержит пять целых чисел n, s[1], v[1], s[2], v[2], указывающих на размер сундука n, а также размер и стоимость изумруда s[1] и v[1], и сапфира s[2], v[2]. Все числа являются натуральными и помещаются в 32-бита.

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

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

Пример

Входные данные #1
2
100 1 1 2 2
100 34 34 5 3
Выходные данные #1
Case #1: 100
Case #2: 86
Источник 2011 ACM Asia Shanghai Regional Contest, Fudan University, Октябрь 16, Задача A