Провальне ЗНО

Обмеження: 2 сек., 256 МіБ

Після поганого результату на ЗНО Зеник відправився в армію. Батько Марічки був командиром полку, а тому Зеник був головним серед кадетів.

Отож Зенику доручили серед \(n\) кадетів обрати \(k\). Він вирішив, що потрібно усіх кадетів вишикувати в шеренгу й виконати декілька разів таку дію.

• Вибрати одного з кадетів, що залишились.

• Тоді вибрати, чи цей кадет виштовхає із шеренги всіх кадетів правіше або лівіше.

• Виштовхнути всіх кадетів у вибраному напрямку. За кожного виштовханого кадета потрібно заплатити однакову ціну.

Для кожного кадета в початковій шерензі Зеник знає ціну за одного виштовханого ним кадета. У Зеника проблеми з математикою, саме тому він опинився в армії.

Він просить вас порахувати мінімальну кількість гривень, яку він має заплатити, щоб отримати шеренгу з рівно \(k\) кадетів.

Вхідні дані

У першому рядку задано два цілих числа \(n\) і \(k\) — початкову й кінцеву кількості кадетів у шерензі відповідно.

У другому рядку задано \(n\) цілих чисел \(a_i\) — кількість гривень, що потрібно заплатити \(i\)-ому кадетові за одного виштовхнутого кадета.

Вихідні дані

У єдиному рядку виведіть ціле число — мінімальну кількість гривень, необхідну Зеникові, щоб звузити шеренгу до \(k\) кадетів.

Обмеження

\(1 \le k \le n \le 10^5\),

\(1 \le a_i \le 10^9\),

для 13 тестів виконується додаткове обмеження \(n \le 1000\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 4 4 7 7 4 4 7 7	12

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
6 2 1 3 4 2 5 6	10

Примітки

У першому тесті четвертий кадет виштовхає трьох кадетів справа, і Зеник заплатить за це \(3 \cdot a_4 = 3 \cdot 4 = 12\) (грн).

У другому тесті четвертий кадет виштовхає двох кадетів справа, після чого другий кадет також виштовхає двох кадетів справа. Загалом Зеник заплатить \(2 \cdot a_4 + 2 \cdot a_2 = 2 \cdot 2 + 2 \cdot 3 = 10\) (грн).