Вам задано послідовність цілих чисел \(A=(A_1,A_2,\dots,A_N)\) довжини \(N\).

Знайдіть максимальне значення \(\displaystyle \sum_{i=1}^{M} i \times B_i\) для (не обов’язково суміжної) підпослідовності \(B=(B_1,B_2,\dots,B_M)\) довжини \(M\) від \(A\).

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

Наприклад, (10,30) є підпослідовністю (10,20,30), але (20,10) не є підпослідовністю (10 ,20,30).

Обмеження

• \(1 \le M \le N \le 2000\)
• \(- 2 \times 10^5 \le A_i \le 2 \times 10^5\)
• Усі значення у вхідних даних є цілими числами.

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

Перший рядок містить цілі числа \(N,M\)

Наступний  рядок містить \(N\) цілих чисел \(A_i\)

Числа у рядках розділяються пропуском.

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

У вихідний потік виведіть відповідь.

Примітка

До прикладу 1:

Коли \(B=(A_1,A_4)\), маємо \(\displaystyle \sum_{i=1}^{M} i \times B_i\) = \(1 \times 5 + 2 \times 8\) = 21. Оскільки неможливо досягти 22 або більшого значення, рішенням буде 21.

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

4 2
5 4 -1 8

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

21

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

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

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

54