Вам задано послідовність цілих чисел \(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)\) послідовності \(A\) довжини \(M\).

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

Наприклад, (2, 3) і (1, 2, 3) є суміжними підмасивами (1, 2, 3, 4), але (1, 3) і (3,2,1) не є суміжними підмасивами (1, 2, 3, 4).

Обмеження

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

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

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

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

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

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

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

Примітка

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

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

Зверніть увагу, що вам не дозволено вибирати, наприклад, \(B=(A_1,A_4)\).

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

4 2
5 4 -1 8

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

15

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

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

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

31