Непроста подорож

Limits: 2 sec., 256 MiB

Невід’ємною складовою участі у Всеукраїнській олімпіаді є подорож до міста, що приймає Всеукраїнську олімпіаду. Цього року вам доведеться відвідати славне місто Хмельницький. Кожна мандрівка залишає за собою незабутній багаж спогадів!

Чисто гіпотетично, перед поїздкою до Хмельницького вам доведеться відвідати ще деяку кількість міст. Кожне із цих міст має свою цікавість — натуральне число \(a_i\). Відвідини кожного міста будуть вас дуже втомлювати. Якщо ви відвідаєте \(i\)-е місто \(k\)-м по порядку, то ваша втома збільшиться на число рівне \(a_i \cdot k\). Якщо ви прийшли в якесь місто вперше, ви мусите його відвідати. Якщо ви проходите повз нього після цього, ви його вже не відвідуєте.

Може так статися, що всі ці міста будуть розташовані на одній прямій, і з кожного міста можна буде потрапити лише в його безпосереднього лівого або правого сусіда (окрім першого та останнього міст — з них можна потрапити лише в одне місто).

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

Допоможіть же собі, напишіть для цього програму.

Input

Перший рядок містить два натуральні числа \(n\) і \(s\) — кількість міст і номер міста, в якому ви початково стоїте (нумерація з 1).

Другий рядок містить \(n\) натуральних чисел \(a_i\) — цікавості кожного міста. Міста задані в такому порядку, в якому вони розташовані на прямій.

Output

У єдиному рядку виведіть натуральне число — мінімальну втому після відвідин усіх міст.

Constraints

\(40\%\) тестів: \(3 \le n \le 10, 1 \le s \le n, 1 \le a_i \le 10^5\),

\(60\%\) тестів: \(3 \le n \le 10^3, 1 \le s \le n, 1 \le a_i \le 10^5\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 2 1 4 100	207

Notes

Починаємо в другому місті і втомлюємося на \(4\cdot1\) одиницю, потім ідемо в місто №3 і втомлюємося там на \(100\cdot2\) одиниці. Потім ідемо в місто №1 і втомлюємося там на \(1\cdot3\) одиниці. Сумарна втома — 207.