Спайк і Тайк#13006

Спайк і Тайк

Бульдог Спайк знайшов велику смачну кістку, поділену на частин. М’ясистість -ї частини дорівнює a_i.

Він планує поділитися нею зі своїм сином Тайком, але Спайк просто обожнює ламати кістки — щоразу, коли він розколює кістку, це приносить йому особливе задоволення!

За один хід Спайк обирає неперервний фрагмент кістки від позиції до позиції і розколює його в деякій точці (l \le p < r). Після цього кістка розділяється на дві менші частини:

[a_l, a_{l+1}, \dots, a_p] \quad \text{та} \quad [a_{p+1}, a_{p+2}, \dots, a_r].

Нехай

L = \sum_{i=l}^{p} a_i, \quad R = \sum_{i=p+1}^{r} a_i.

Після розколу загальне задоволення Спайка збільшується на L \times R.

Після кожного розколу загальна кількість неперервних шматків кістки збільшується на один. Шматки розміру більше не можна розколоти — вони занадто малі.

Спайк хоче виконати рівно розколів так, щоб його сумарне задоволення було максимальним.

Знайдіть максимально можливе сумарне задоволення після рівно розколів.

Input

У першому рядку задано два цілі числа та — розмір масиву та кількість розколів, які хоче виконати Спайк.

У другому рядку задано цілих чисел a_1, a_2, \dots, a_n — значення м’ясистості частин кістки.

1 \le k < n \le 10^5,

0 \le a_i \le 10^4.

Output

Виведіть одне ціле число — максимально можливе сумарне задоволення після рівно розколів.

Examples

Example

Loading
Loading

Example 1

Loading
Loading