Задача Tram. Керівництво Муніципальної Транспортної Компанії м. Вінниці вирішило встановити нову систему оплати за проїзд у трамваях. Маршрут являє собою відрізок прямої, на якій послідовно розміщені N зупинок. Планується розбити їх на M неперервних зон, що слідують підряд, таким чином, щоб кожна зона містила хоча б одну зупинку. Оплату проїзду від зупинки i до зупинки k необхідно встановити рівною 1+|zi−zk|, де zi і zk ‑ номери зон, яким належать зупинки i та k відповідно.
Відома кількість пасажирів, які відправляються за день з кожної зупинки на кожну іншу. Напишіть програму, що визначає, яку максимальну суму грошей за день можна отримати за новою системою при оптимальному розбитті на зони.
Технічні умови. Програма Tram зчитує зі стандартного пристрою введення 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 |