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

Обмеження: 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$ (грн).