Statement is not available in English language
4. Оптимальные тарифы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На уроке информатики Маша и Петя узнали, что любое натуральное число представимо в виде суммы различных степеней двойки единственным образом. Таким образом у них появилась идея модернизации тарифов сотовых операторов. Действительно, почему бы не продавать пакеты по 1, 2, 4, 8, ... минут разговоров, чтобы каждый мог набрать столько минут, сколько ему нужно?

Согласовав все тонкости, Маша с Петей предложили однокласснику Вите тарифный план, состоящий из $$$n$$$ предложений: $$$i$$$-е предложение (начиная с 0) представляет собой пакет на $$$2^i$$$ минут со стоимостью $$$a_i$$$ рублей, причем из соображений адекватности цены $$$a_i \leqslant 2^i$$$ и $$$a_i \leqslant a_{i + 1}$$$.

Вите нужны хотя бы $$$k$$$ минут разговоров для его нужд, и, естественно, он хочет сэкономить как можно больше денег. Напишите программу, которая выведет минимальное количество денег, которые необходимо потратить Вите по тарифному плану Маши и Пети, если можно покупать несколько одинаковых пакетов.

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

В первой строке ввода дается одно число $$$k$$$ $$$(1 \leqslant k \leqslant 10^9)$$$ — количество минут разговоров, необходимых Вите. Во второй строке находится число $$$n$$$ $$$(1 \leqslant n \leqslant 100)$$$ — количество тарифов, предлагаемых Машей и Петей. В третьей строке находятся $$$n$$$ чисел — $$$a_0$$$, $$$a_1$$$, ..., $$$a_{n-1}$$$ $$$({1 \leqslant a_i \leqslant \text{min}(2^i, 10^9)}$$$, $$${a_i \leqslant a_{i + 1}})$$$ — стоимости соответствующих пакетов минут.

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

Выведите одно число — минимальное количество денег (в рублях), которое необходимо Вите, чтобы суммарное количество минут в купленных пакетах было не меньше $$$k$$$.

Система оценки

Гарантируется, что решения, корректно работающие при ограничении $$$k \leqslant 10^7$$$, будут оцениваться исходя из 75 баллов.

Пример
Входные данные
23
5
1 2 3 7 16
Выходные данные
18
Примечание

В примере пакет на 1 минуту стоит 1 рубль, на 2 минуты — 2 рубля, на 4 минуты — 3 рубля, на 8 минут — 7 рублей и на 16 минут — 16 рублей. Выгоднее всего взять 6 пакетов по 4 минуты (суммарно 24 минуты), тем самым Вите необходимо иметь хотя бы $$$6 \times 3 = 18$$$ рублей.