Повторне відвідування круглого амбару#10587

Повторне відвідування круглого амбару

1 секунда

128 мегабайтів

Складна

Корівник складається з кільця з $n$ кімнат, пронумерованих за годинниковою стрілкою від $1$ до $n$ по периметру корівника. Кожна кімната має двері, що з'єднують її з двома сусідніми кімнатами, а також двері, що ведуть назовні з корівника.

Фермер Джон хоче, щоб у кімнаті $i$ опинилося рівно $r_{i}$ r_i корів. Щоб організовано загнати корів у корівник, він планує відкрити $k$ зовнішніх дверей, дозволивши коровам входити лише через ці двері. Після входу кожна корова рухається за годинниковою стрілкою через кімнати, поки не досягне відповідного місця призначення. Фермер Джон хоче вибрати $k$ зовнішніх дверей таким чином, щоб після входу в корівник корови в сукупності пройшли мінімально можливу суммарну відстань. Спочатку корови можуть вишикуватися в будь-якому порядку зовні $k$ відкритих дверей, і це не враховується в загальній пройденій відстані. Визначте мінімальну суммарну відстань, яку повинні пройти корови, якщо Фермер Джон вибере оптимальні $k$ дверей для відкриття.

Вхідні дані

У першому рядку містяться два цілих числа $n (3 \leq n \leq 100)$ n~(3 \le n \le 100) та $k (1 \leq k \leq 7)$ k~(1 \le k \le 7). У наступних $n$ рядках міститься по одному цілому числу $r_{i} (1 \leq r_{i} \leq 1 0^{6})$ r_i~(1 \le r_i \le 10^6), де $r_{i}$ r_i — кількість корів, які повинні опинитися в кімнаті $i$ .

Вихідні дані

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

Приклади

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

Приклад 1