409731: GYM103714 A Диплом

A. Дипломограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Артем наконец написал свою дипломную работу! Теперь ее надо напечатать и отдать коммисии на проверку. Правда кризис ударил в самый неподходящий момент — бумага формата А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