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