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

У фермера Джона є круглий амбар, що складається з кільця з 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.