Đ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) = Σ(Ak + 1 - Ak), k = 1 .. n - 1
gde Ai 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 Ai (-1.000.000 ≤ Ai ≤ 1.000.000), u i-tom redu broj Ai.
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.
standardni ulaz | standardni izlaz | |
---|---|---|
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.
standardni ulaz | standardni izlaz | |
---|---|---|
3 1 10 9 8 |
-1 |
Comments