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. \InputFile 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)$. \OutputFile Print the smallest possible value of the largest number written on the board. \Examples 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 $$