Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

The teacher writes numbers $a_{1},a_{2},...,a_{n}$ on the board. Then, until the count of numbers written on the board reaches $m$, the students approach the board one by one, choose any two consecutive numbers currently written on the board, and write the sum of these two numbers between them.

Find the smallest possible value of the largest number written on the board.

The first line contains two integers $n$ and $m(2≤n≤m≤10_{5})$. The next line contains $n$ integers $a_{1},a_{2},...,a_{n}(1≤a_{i}≤10_{6})$.

Print the smallest possible value of the largest number written on the board.

Example 1.

$1,1→1,2,1→1,3,2,1→1,3,2,3,1$

Example 2.

$4,6,3→4,6,9,3$

Input #1

Answer #1

Input #2

Answer #2

Input #3

Answer #3