Задача Станции (STATIONS)

Руководство Очень Большой Железной Дороги (ОБЖД) решило установить новую систему оплаты за проезд. ОБЖД представляет собой отрезок прямой, на которой последовательно размещены 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.

Программа должна вывести на стандартное устройство вывода единственное целое число ‑ искомую максимальную дневную выручку.

Пример: