Повторний візит до круглого амбару

У фермера Джона є круглий амбар, що складається з кільця з n кімнат, пронумерованих від 1 до n по периметру. Кожна кімната має двері, що ведуть до двох сусідніх кімнат, а також одні двері, що ведуть назовні.

Фермер Джон планує розмістити рівно r[i] корів у кімнаті i. Він збирається відкрити k зовнішніх дверей, через які корови зможуть увійти в амбар. Після входу кожна корова рухається за годинниковою стрілкою, поки не досягне своєї призначеної кімнати. Фермер Джон хоче відкрити двері так, щоб загальна відстань, яку пройдуть усі корови, була якомога меншою. Корови можуть попередньо зібратися перед відкритими дверима, і ці переміщення не враховуються в загальній відстані. Визначте мінімальну сумарну відстань, яку доведеться пройти коровам, якщо фермер Джон оптимально вибере, які k дверей відкрити.

Вхідні дані

Перша стрічка містить n (3 ≤ n ≤ 100) і 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.