Руководство Очень Большой Железной Дороги (ОБЖД) решило установить новую систему оплаты за проезд. ОБЖД представляет собой отрезок прямой, на которой последовательно размещены \textbf{n }станций. Планируется разбить их на \textbf{m }подряд идущих непрерывных зон, каждая из которых содержит хотя бы одну станцию, и установить оплату проезда от станции \textbf{i} до станции \textbf{k}, равную \textbf{1} + |\textbf{z_i} − \textbf{z_k}|, где \textbf{z_i} и \textbf{z_k} ‑ номера зон, которым принадлежат станции \textbf{i} и \textbf{k} соответственно. Известно количество пассажиров, которое отправляется за день с каждой станции на каждую другую. Напишите программу, определяющую, какую максимальную дневную выручку можно получить по новой системе при оптимальном разбиении на зоны. \InputFile Программа считывает \textbf{n }строк. Первая строка содержит два целых числа \textbf{n} и \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{n} ≤ \textbf{1000}). Вторая -- одно число, обозначающее количество пассажиров, едущих от станции \textbf{1 }до станции \textbf{2}. Третья -- два числа, обозначающих количество пассажиров, едущих от станции \textbf{1} до станции \textbf{3} и от станции \textbf{2 }до станции \textbf{3}, соответственно. И так далее. В \textbf{n}-ой строке содержится \textbf{n} − \textbf{1} число, \textbf{i}-ое из них определяет количество пассажиров от станции \textbf{i} до станции \textbf{n}. Количество пассажиров для каждой пары станций дано с учетом движения в обе стороны. Все числа целые неотрицательные и не превосходят \textbf{10000}. \OutputFile Вывести искомую максимальную дневную выручку.