Đurica je pronašao n karata poređanih u niz. Na kartama su zapisani celi brojevi.Datom nizu karata A, Đurica dodeluje vrednost f(A) koja je jednaka sumi razlika vrednostina uzastopnim kartama. Formalno,
f(A) = Σ(A_{k + 1} - A_k), k = 1 .. n - 1
gde A_i predstavlja vrednost na i-toj karti u nizu.

Đurica iz niza želi da izbaci najviše K karata. Izbacivanjem nekih m karata, m ≤ K, dobija nov niz karata kojem ponovo računa vrednost na opisani način. Od svih mogućih odabira vrednosti m i svih mogućih odabira m karata koje će izbaciti, njega zanima onaj niz karata koji će imati najveću vrednost. Pomozite Đurici i recite mu koliko je ta najveća vrednost. Primetimo da Đurica ni u jednom momentu ne menja raspored karata datih na početku.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu nalaze se celi brojevi n (2 ≤ n ≤ 500.000) i K (0 ≤ K ≤ n - 2). U narednom redu se učitavaju celi brojevi A_i (-1.000.000 ≤ A_i ≤ 1.000.000), u i-tom redu broj A_i.

Izlaz.

(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom redu ispisati jedan ceo broj koji predstavlja najveću vrednost niza koju Đurica može da dobije od početnog izbacivanjem najviše K karata.

Primer 1.

11 4
1 7 2 5 3 8 2 3 6 5 5

5

Objašnjenje.

Jedno optimalno rešenje je da se izbacimo 3 karte iz niza. Karte koje treba izbaciti imaju na sebi vrednost 5.

Primer 2.

3 1
10 9 8

-1