Ви відповідаєте за призначення охоронців у в'язницю, куди відправляють найбожевільніших злочинців. Клітини утворюють один ряд і нумеруються від 1 до \(L\). У камері \(i\) міститься рівно один божевільний, рівень божевілля якого \(C_i\).

Кожен божевільний повинен мати одного охоронця, який стежить за ним/нею. В ідеалі у вас повинен бути один охоронець, який стежить за кожним божевільним. Однак через бюджетні обмеження вам потрібно призначити лише \(G\) охоронців. Ви повинні призначити, за якими божевільними повинен стежити кожен охоронець, щоб мінімізувати загальний ризик того, що хтось втече.

Звичайно, ви повинні призначити кожного охоронця набору суміжних клітин. Рівень ризику \(R_i\), від якого залежить втеча божевільного у камері, визначається добутком його/її рівня божевілля на кількість божевільних, за якими його/її наглядає призначений охоронець. Отримання суми \(R_i\) від \(i=1\) до \(i=L\) дасть нам загальну кількість ризиків \(R\), від яких залежить втеча злочинця.

Враховуючи \(L\) злочинців і \(G\) охоронців, яке мінімально можливе значення \(R\)?

обмеження

• \(1 \le L \le 8000\)
• \(1 \le G \le 800\)
• \(1 \le C_i \le 10^9\)

Формат вхідних даних

Перший рядок містить два натуральні числа, розділені пробілами: \(L\) і \(G\) кількість злочинців і кількість охоронців відповідно.

Наступні \(L\) рядки описують рівень божевілля кожного з божевільних. \(i\)-й рядок описують рівень божевілля божевільного в камерному блоку \(i\).

Формат вихідних даних

Виведіть рядок, що містить мінімально можливе значення \(R\).

Приклад вхідних даних

6 3
11
11
11
24
26
100

Приклад вихідних даних

299

Пояснення

Першого охоронця слід призначити стежити за першими трьома божевільними, кожен з яких має рівень божевілля 11. Другий охоронець повинен бути призначений стежити за наступними двома божевільними, які мають рівні божевілля 24 і 26. Третій охоронець повинен бути призначений найбожевільнішому, тому, хто має рівень божевілля 100.

Кожен із перших трьох божевільних має рівень ризику 33, добуток 11 (рівня божевільності) і 3 (кількості божевільних, за якими стежить їхній охоронець). Наступні три божевільні мають рівень ризику 48, 52 і 100. Додавши це, загальний рівень ризику становить 299.

Приклад вхідних даних