409731: GYM103714 A Диплом
Description
Артем наконец написал свою дипломную работу! Теперь ее надо напечатать и отдать коммисии на проверку. Правда кризис ударил в самый неподходящий момент — бумага формата А4 для печати стала неоправданно дорогой!
Артем расстроился, ведь без бумаги ему никак не получить свой диплом. Но унывал он недолго. Артем увидел в магазине, что бумаги других форматов стоят дешевле! У него появилась гениальная идея — разрезать листы других форматов и получить А4. Он знал, что если разрезать бумагу формата А0, получится два листа формата А1, если А1, то получится два листа А2, и так далее до долгожданного А4!
В магазине ему разъяснили правила покупки бумаги — нельзя покупать бумагу разных форматов, можно выбрать только один, но в неограниченных количествах, мол, так магазин борется с кризисом.
Артем начал считать в уме, сколько ему нужно денег и какой формат лучше взять, но его одногруппники тоже попросили напечатать свои дипломные работы, поэтому ему нужна помощь!
Помогите Артему посчитать минимальную стоимость необходимой бумаги, чтобы напечатать диплом!
Входные данныеПервая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^9$$$) — количество листов в дипломной работе, которую необходимо напечатать.
Следующие пять строк содержат пять целых чисел $$$A_0$$$, $$$A_1$$$, $$$A_2$$$, $$$A_3$$$, $$$A_4$$$ ($$$1 \le A_0, A_1, A_2, A_3, A_4 \le 10^9$$$) — стоимости одного листа бумаги формата A0, A1, A2, A3 и A4 соответственно.
Выходные данныеВыведите единственное число — миниальную стоимость купленной бумаги.
ПримерыВходные данные10 150 80 25 20 100Выходные данные
75Входные данные
1 10 20 30 40 50Выходные данные
10