Reduce the array

Given an array of $n$ integers and an integer $k$. Find the minimum cost to reduce the array to a single element. You can perform the following operation any number of times:

• Choose any pair of consecutive elements $a_i$ and $a_{i+1}$, and replace them with $(a_i+a_{i+1})$. The cost of this operation is $k\cdot (a_i+a_{i+1})$.

Input

The first line contains two integer $n$ and $k(n,k\le 100)$. The second line contains $n$ integers $a_1,a_2,\dots ,a_n(0\le a_i\le 100)$.

Output

Print the minimum cost to reduce the array to a single element.

Examples