For her final CS project, Mafuyu needs to build a tree with $N$ nodes. Where is she going to get the nodes from? The convenience store, of course! The convenience store offers a wide variety of nodes for various prices. Specifically, for each $1\le i\le K$, it has an unlimited supply of nodes with $i$ connectors coming out of it for $a_i$ yen each.

After buying the required nodes, Mafuyu needs to go home and actually build the tree by repeatedly melding two connectors from two different nodes into a single edge connecting the two nodes. The final product should not have any leftover connectors that are not melded.

Given these conditions, please find the minimum total cost required for Mafuyu to build a tree with $N$ nodes!

Constraints

$3\le N\le {10}^9$

$2\le K\le 3\times {10}^3$

$K<N$

$1\le a_i\le {10}^9$

Subtask 1 [15%]

$N\le 300$

Subtask 2 [20%]

$N\le 3\times {10}^3$

Subtask 3 [20%]

$N\le 2\times {10}^5$

$K\le 300$

Subtask 4 [20%]

$K\le 300$

Subtask 5 [25%]

No additional constraints.

Input Specification

The first line contains $2$ space-separated integers $N$ and $K$.

The next line contains $K$ space-separated integers $a_1,a_2,\dots ,a_K$.

Output Specification

Output the minimum total cost (in yen) required for Mafuyu to build a tree with $N$ nodes.

Sample Input

4 3
1 3 4

Sample Output

7

Explanation

Mafuyu can buy $3$ nodes with $1$ connector and $1$ node with $3$ connectors, forming the following tree: