Problem description

Maciej jest koneserem frytek belgijskich. Ciężko dogodzić jego wymaganiom, z tego powodu co roku, w każdą jesień, samodzielnie wybiera się na pole ziemniaków, żeby wybrać ziemniaki najlepszej jakości. Pole składa się z jednej, długiej grządki, w której rośnie N ziemniaków, jeden za drugim. Maciej każdemu ziemniakowi przypisuje pewien stopień okazałości A_i. Oczywiście im ziemniak jest bardziej okazały, tym lepiej.

Maciejowi do zapasów na następny rok potrzebne jest dokładnie K ziemniaków. Zależy mu na tym, żeby sumaryczny stopień okazałości ziemniaków był jak największy. Z drugiej strony zdaje sobie sprawę, że ziemniaki, które rosną w dużej odległości od siebie, będą się od siebie znacząco różniły. Stąd dla danego podciągu ziemniaków (A_i1,…,A_iK), gdzie i₁ < i₂ < …i_K, jego jakość Maciej oblicza jako sumę okazałości ziemniaków minus różnicę odległości dwóch najbardziej odległych ziemniaków, tj.:

$$(\sum^K_{j=1}A_{i_j}) - (i_K - i_1)^2$$

Maciej wyznaczył Ciebie do znalezienia najlepszego podciągu ziemniaków, a w zamian podzieli się z Tobą pysznymi frytkami. Pomóż mu i napisz program, który wyznaczy maksymalną możliwą jakość podciągu K ziemniaków.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby naturalne N, K oznaczające długość grządki ziemniaków oraz liczbę ziemniaków potrzebnych Maciejowi. W następnym wierszu następuje N nieujemnych liczb całkowitych A₁, A₂, …, A_N oznaczających okazałości kolejnych ziemniaków w grządce.

Wyjście

W pierwszym (jedynym) wierszu standardowego wyjścia powinna się znaleźć jedna liczba całkowita oznaczająca maksymalną możliwą jakość podciągu K ziemniaków.

Ograniczenia

2 ≤ K ≤ N ≤ 200 000, 1 ≤ A_i ≤ 10¹².

Przykład

6 3
2 8 1 3 7 3 

9