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