Бульдог Спайк знайшов велику смачну кістку, поділену на частин. М’ясистість -ї частини дорівнює a_i.
Він планує поділитися нею зі своїм сином Тайком, але Спайк просто обожнює ламати кістки — щоразу, коли він розколює кістку, це приносить йому особливе задоволення!
За один хід Спайк обирає неперервний фрагмент кістки від позиції до позиції і розколює його в деякій точці (l \le p < r). Після цього кістка розділяється на дві менші частини:
Нехай
Після розколу загальне задоволення Спайка збільшується на L \times R.
Після кожного розколу загальна кількість неперервних шматків кістки збільшується на один. Шматки розміру більше не можна розколоти — вони занадто малі.
Спайк хоче виконати рівно розколів так, щоб його сумарне задоволення було максимальним.
Знайдіть максимально можливе сумарне задоволення після рівно розколів.
У першому рядку задано два цілі числа та — розмір масиву та кількість розколів, які хоче виконати Спайк.
У другому рядку задано цілих чисел a_1, a_2, \dots, a_n — значення м’ясистості частин кістки.
1 \le k < n \le 10^5,
0 \le a_i \le 10^4.
Виведіть одне ціле число — максимально можливе сумарне задоволення після рівно розколів.
Example
Example 1