The teacher writes numbers on the board. Then, until the count of numbers written on the board reaches , 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 and . The next line contains integers .
Print the smallest possible value of the largest number written on the board.
Example 1.
Example 2.