Đ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 vrednosti na 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 iz datoteke sumarum.in.) 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.

(Izlazne podatke upisati u datoteku sumarum.out) 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

/*
  Autor: Slobodan Mitrovic
*/
#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <cmath>
#include <time.h>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)

using namespace std;

const int MAXN = 500000;

int mmax[MAXN], mmin[MAXN], a[MAXN];

int main(){
  FILE *fin;
  FILE *fout;
  fin = fopen("sumarum.in", "r");
  fout = fopen("sumarum.out", "w");
    
  int n, k;
  fscanf(fin, "%d %d", &n, &k);
  FOR (i, n)
    fscanf(fin, "%d", &a[i]);
  
  mmax[n - 1] = a[n - 1];
  for (int i = n - 2; i > -1; i--)
    mmax[i] = max(a[i], mmax[i + 1]);
    
  
  mmin[0] = a[0];
  ffor (i, 1, n)
    mmin[i] = min(a[i], mmin[i - 1]);
      
  int idxLeft = 0, idxRight = n - k - 1, ret = -(1 << 30);
  FOR (i, k + 1){
    ret = max(ret, mmax[idxRight] - mmin[idxLeft]);
    idxLeft++;
    idxRight++;
  }
  
  fprintf(fout, "%d\n", ret);
  fclose(fin);
  fclose(fout);
  return 0;
}

(* Autor: Slobodan Mitrovic *)
program sumarum;
var
  mmax, mmin, a : array [0 .. 499999] of longint;
  n, k, i, idxLeft, idxRight, ret : longint;
  f : text;
  
function max(x, y : longint) : longint;
begin
  if (x > y) then
    max := x
  else
    max := y;
end;

function min(x, y : longint) : longint;
begin
  if (x < y) then
    min := x
  else
    min := y;
end;

begin
  assign(f, 'sumarum.in');
  reset(f);
  readln(f, n, k);
  for i := 0 to n - 1 do
    read(f, a[i]);
    
  mmax[n - 1] := a[n - 1];
  for i := n - 2 downto 0 do
    mmax[i] := max(a[i], mmax[i + 1]);
      
  mmin[0] := a[0];
  for i := 1 to n - 1 do
    mmin[i] := min(a[i], mmin[i - 1]);
        
  idxLeft := 0;
  idxRight := n - k - 1;
  ret := -1000000000;
  for i := 0 to k do
    begin
      ret := max(ret, mmax[idxRight] - mmin[idxLeft]);
      inc(idxLeft);
      inc(idxRight);
    end;
  
  dec(idxRight);
  dec(idxLeft);
  assign(f, 'sumarum.sol');
  rewrite(f);
  writeln(f, ret);
  close(f);
end.