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