Уменьшить массив

Задан массив, состоящий из $n$ целых чисел, и число $k$. Найдите минимальную стоимость сведения массива до одного элемента. Вы можете выполнять следующую операцию любое количество раз:

• Выберите любую пару соседних элементов $a_i$ и $a_{i+1}$ и замените их на $(a_i+a_{i+1})$. Стоимость такой операции равна $k\cdot (a_i+a_{i+1})$.

Входные данные

Первая строка содержит два натуральных числа $n$ и $k(n,k\le 100)$. Вторая строка содержит $n$ целых чисел $a_1,a_2,\dots ,a_n(0\le a_i\le 100)$.

Выходные данные

Выведите минимальную стоимость сведения массива до одного элемента.

Примеры