Reduce the array

Given an array consisting 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 array elements $a_i$ and $a_j$ and replace them with $(a_i+a_{i+1})$ at a cost of $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