Керівництво Дуже Великої Залізниці (ДВЗ) вирішило встановити нову систему оплати за проїзд. ДВЗ являє собою відрізок прямої, на якій послідовно розміщені N станцій. Планується розбити їх на M неперервних зон, що слідують підряд, таким чином, щоб кожна зона містила хоча б одну станцію. Оплату проїзду від станції i до станції k необхідно встановити рівною 1+|z_i−z_k|, де z_i і z_k ‑ номери зон, яким належать станції i та k відповідно. Відома кількість пасажирів, які відправляються за день з кожної станції на кожну іншу. Напишіть програму, що визначає, яку максимальну денну виручку можна отримати за новою системою при оптимальному розбитті на зони. \InputFile Програма зчитує зі стандартного пристрою введення N рядків. Перший рядок містить два цілих числа N та M (1≤M≤N≤1000). Другий -- одне число, що означає кількість пасажирів, що їдуть від станції 1 до станції 2. Третя -- два числа, що означають кількість пасажирів, що їдуть від станції 1 до станції 3 та від станції 2 до станції 3, відповідно. І так далі. В N-ому рядку міститься N−1 число, i-е з них визначає кількість пасажирів від станції i до станції N. Кількість пасажирів для кожної пари станцій дано з урахування руху в обидві сторони. Всі числа цілі невід’ємні та не перевищують 10000. \OutputFile Програма повинна вивести на стандартний пристрій виведення єдине ціле число -- шукану максимальну денну виручку.