Зменшити масив

Задано масив, що складається з $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)$.

Вихідні дані

Виведіть мінімальну вартість зведення масиву до одного елемента.

Приклади