F. Festa Junina
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The "Festa Junina", a traditional celebration in Brazil, organized by BRUTE (Bureau for Realization of Unique and Triumphant Events), always features various notable personalities. In the 2023 edition, some of the attendees were acclaimed football players: Gasparinius Jr. and Karinen Sousa.

Upon seeing Gasparinius at the party, Karinen decides to pay a fee of R$ 2.00 to send him to "jail". The "jail" is a common game at Festas Juninas, but BRUTE came up with their own version. In it, whoever is jailed is kept in a locked room indefinitely and is only released when the bail is paid. This measure was necessary because the Bureau was out of budget for upcoming events after impulsively buying a sofa for their office.

Thus, Gasparinius was taken by the BRUTE guards to the jail, where he was eager to know the cost of his bail. The guards told him:

"The cost of your bail will be the cost of a sequence of exactly $$$N$$$ integers you present to us, being strictly ascending (each element is greater than the previous one) and only containing numbers greater than zero. The cost of a sequence is given by the sum of the costs of each of its elements. The cost of an element $$$x$$$ is determined by its binary representation, with each binary digit $$$i$$$ (corresponding to $$$2^i$$$) associated with a cost we call $$$C_i$$$, which will be added to the total if, and only if, the digit in that position is '1'. Again, the cost of the number $$$x$$$ will be the sum of the $$$C_i$$$ for all $$$i$$$ where the digit is '1' in the binary representation of $$$x$$$. We will give you $$$M$$$ cost values, which we guarantee will suffice for the binary representation of at least the $$$N$$$-th number."

Even though it wasn't a real jail, BRUTE is very strict about security and allows those jailed to make only one phone call. Gasparinius Jr. decides to use his call to contact you. Knowing your ability to solve problems like this, he asks you to write a program that calculates the lowest possible cost of a sequence to minimize his bail expenses.

Input

The first line contains the integers $$$N$$$ $$$(1 \leq N \leq \min(2^M-1,100))$$$, the size of the sequence you should consider, and $$$M$$$ $$$(1 \le M \le 1000)$$$, the amount of costs associated with binary digits. The second line contains $$$M$$$ integers $$$C_i$$$ $$$(0 \leq i \lt M, 1 \le C_i \le 10^9)$$$ representing the cost of the binary digit $$$i$$$ for all elements of the sequence.

Output

Print a single value, the minimum cost among all possible sequences of size $$$N$$$.

Examples
Input
3 3
1 1 1
Output
3
Input
3 3
1 2 4
Output
6
Input
3 3
4 2 1
Output
6
Note

In the first example, the sequence $$$[1, 2, 4]$$$ has a total value of R$3.00.

In the second example, we can construct the sequence $$$[1, 2, 3]$$$, with a value of R$6.00.

Finally, the sequence $$$[2, 4, 6]$$$ results in the lowest value (R$6.00) for example 3.