Hay \(N\) slimes alineados en una fila. Inicialmente, el i-ésimo slime desde la izquierda tiene un tamaño de \(a_i\).

Taro está intentando combinar todos los slimes en un slime más grande. Realizará la siguiente operación repetidamente hasta que haya solo un slime:

• Elige dos slimes adyacentes y los combina en un nuevo slime. El nuevo slime tiene un tamaño de \(x + y\), donde \(x\) e \(y\) son los tamaños de los slimes antes de combinarlos. Aquí, se incurre en un costo de \(x + y\). La relación posicional de los slimes no cambia al combinarlos.

Encuentra el mínimo costo total posible para combinar todos los slimes.

Entrada

La primera linea contiene un \(N\) y \(K\), el numero de slimes (\(2 \leq N \leq 400\)).

La segunda linea contiene \(N\) enteros \(a_1,a_2,\dots,a_N\), los tamaños iniciales de los slimes (\(1 \leq h_i \leq 10^9\)).

Salida

Imprimir un solo número: el mínimo costo total posible para combinar todos los slimes.

Ejemplo

Entrada 1

4
10 20 30 40

Salida 1

190

Entrada 2

5
10 10 10 10 10

Salida 2

120