#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,K,Ks,niz[200005],res,zl,zr,br;
const int prom=100001;
int vel[5];
struct slog{
   int veci,manji,kol;
}st[5][525000];
void update(int gde,int in){
   gde/=2;
   while(gde>=1){
      st[in][gde].manji=min(st[in][gde*2].manji,st[in][gde*2+1].manji);
      st[in][gde].veci=max(st[in][gde*2].veci,st[in][gde*2+1].veci);
      gde/=2;
   }
   return;
}
ll getmax(string stablo){
   if(stablo=="L")
      return st[0][1].veci-prom;
   if(stablo=="R")
      return st[1][1].veci-prom;
   if(stablo=="RC")
      return st[2][1].veci-prom;
   if(stablo=="LC")
      return st[3][1].veci-prom;
}
ll getmin(string stablo){
   if(stablo=="L")
      return st[0][1].manji-prom;
   if(stablo=="R")
      return st[1][1].manji-prom;
   if(stablo=="RC")
      return st[2][1].manji-prom;
   if(stablo=="LC")
      return st[3][1].manji-prom;
}
ll getsize(string stablo){
   if(stablo=="L")
      return vel[0];
   if(stablo=="R")
      return vel[1];
   if(stablo=="RC")
      return vel[2];
   if(stablo=="LC")
      return vel[3];
}
void dodaj(string stablo,int broj){
   int ind;
    if(stablo=="L")
      ind=0;
   if(stablo=="R")
      ind=1;
   if(stablo=="RC")
      ind=2;
   if(stablo=="LC")
      ind=3;
   if(ind==0)
      zl+=broj;
   if(ind==1)
      zr+=broj;
   st[ind][broj+prom+Ks-1].kol++;
   vel[ind]++;
   if(st[ind][broj+prom+Ks-1].kol==1){
      st[ind][broj+prom+Ks-1].veci=broj+prom;
      st[ind][broj+prom+Ks-1].manji=broj+prom;
      update(broj+prom+Ks-1,ind);
   }
   return;
}
void skloni(string stablo,int broj){
   int ind;
   if(stablo=="L")
      ind=0;
   if(stablo=="R")
      ind=1;
   if(stablo=="RC")
      ind=2;
   if(stablo=="LC")
      ind=3;
   if(ind==0)
      zl-=broj;
   if(ind==1)
      zr-=broj;
   st[ind][broj+prom+Ks-1].kol--;
   vel[ind]--;
   if(st[ind][broj+prom+Ks-1].kol==0){
      st[ind][broj+prom+Ks-1].veci=-1e9;
      st[ind][broj+prom+Ks-1].manji=1e9;
      update(broj+prom+Ks-1,ind);
   }
   return;
}
bool stavio(string stablo,int broj){
   int ind;
   if(stablo=="L")
      ind=0;
   if(stablo=="R")
      ind=1;
   if(stablo=="RC")
      ind=2;
   if(stablo=="LC")
      ind=3;
   return (st[ind][broj+prom+Ks-1].kol>0);
}
void izracunaj(){
   zl=zr=0;
   for(int i=1;i<=Ks+Ks;i++){
      st[0][i].manji=1e9;
      st[0][i].veci=-1e9;
      st[0][i].kol=0;
      st[1][i]=st[0][i];
      st[2][i]=st[0][i];
      st[3][i]=st[0][i];
   }
   vel[0]=vel[1]=vel[2]=vel[3]=0;
   dodaj("L",niz[1]);
   for(int i=2;i<=N;i++){
      dodaj("R",niz[i]);
      if(getsize("R")+1>K){
         br=getmax("R");
         dodaj("RC",br);
         skloni("R",br);
      }
   }
   res=max(res,zr-zl);
   res=max(res,zl-zr);
   //cout<<res<<endl;
   for(int i=2;i<N;i++){
      dodaj("LC",niz[i]);
      if(stavio("RC",niz[i])){
         skloni("RC",niz[i]);
      }
      else{
         skloni("R",niz[i]);
         if(getsize("RC")!=0){
            br=getmin("RC");
            dodaj("R",br);
            skloni("RC",br);
         }
         else{
            br=getmax("LC");
            dodaj("L",br);
            skloni("LC",br);
         }
      }
      while(getsize("LC")>0){
         if(getmin("L")>=getmax("LC"))
            break;
         br=getmax("LC");
         dodaj("L",br);
         skloni("LC",br);

         br=getmin("L");
         dodaj("LC",br);
         skloni("L",br);
      }
      while(getsize("RC")>0){
         if(getmax("R")<=getmin("RC"))
            break;
         br=getmin("RC");
         dodaj("R",br);
         skloni("RC",br);

         br=getmax("R");
         dodaj("RC",br);
         skloni("R",br);
      }
      while(getsize("L")>1 and getsize("RC")>0){
         if(getmin("L")>=(-getmin("RC")))
            break;
         br=getmin("L");
         dodaj("LC",br);
         skloni("L",br);

         br=getmin("RC");
         dodaj("R",br);
         skloni("RC",br);
      }
      while(getsize("R")>1 and getsize("LC")>0){
         if(getmax("LC")<=(-getmax("R")))
            break;
         br=getmax("R");
         dodaj("RC",br);
         skloni("R",br);

         br=getmax("LC");
         dodaj("L",br);
         skloni("LC",br);
      }
      //cout<<i<<": "<<zl-zr<<endl;
      res=max(res,zr-zl);
      res=max(res,zl-zr);
   }
   return;
}
int main(){
   res=-9e18;
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   cin>>N>>K;
   for(int i=1;i<=N;i++)
      cin>>niz[i];
   Ks=262144;
   izracunaj();
   for(int i=1;i<=N/2;i++)
      swap(niz[i],niz[N-i+1]);
   izracunaj();
   cout<<res<<"\n";
}