Задача Станции (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 |