Круглый амбар (Платина)

У Фермера Джона круглый амбар. Амбар состоит из кольца из n комнат, пронумерованных 1 ... n по периметру. Каждая комната имеет двери в две соседние комнаты и одну дверь во внешний мир.

ФД хочет разместить ровно r[i] коров в комнате i. Он планирует открыть k внешних дверей, через которые коровы будут входить в амбар. Каждая корова затем идёт по часовой стрелке, пока не добредёт до нужной комнаты. ФД хочет открыть двери так, чтобы все коровы вместе прошли как можно меньшее расстояние. Коровы предварительно могут собраться как им выгоднее перед этими незакрытыми дверями (эти перемещения не входят в общее расстояние, учитываемое в задаче). Определите минимальное суммарное расстояние, которое придётся пройти коровам, если ФД наилучшим образом выберет какие k открыть.

Входные данные

Первая строка содержит n (3 ≤ n ≤ 1000) и k (1 ≤ k ≤ 7). Последующие n строк содержат r[1] ... r[n] (1 ≤ r[i] ≤ 10^6).

Выходные данные

Выведите минимальное суммарное расстояние пройденное коровами.

Примеры

Примечание

ФД может открыть двери 2 и 5. 11 коров войдут в двери 2 и пройдут суммарное расстояние 8 чтобы попасть в комнаты 2, 3, 4. 10 коров войдут в дверь 5 и пройдут общее расстояние 6, чтобы попасть в комнаты 5, 6, 1.