Dynamic array

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.

Input

The first line contains two integers $n$ and $m(2\le n\le m\le 10^5)$. The next line contains $n$ integers $a_1,a_2,...,a_n(1\le a_i\le 10^6)$.

Output

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

Examples

Example 1.

Example 2.