#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,K,niz[200005],res,zl,zr;
multiset<ll> L,R,RC,LC;
multiset<ll>::iterator it;
void izracunaj(){
   zl=zr=0;
   L.clear();
   R.clear();
   RC.clear();
   LC.clear();
   L.insert(niz[1]);
   zl=niz[1];
   for(int i=2;i<=N;i++){
      R.insert(niz[i]);
      zr+=niz[i];
      if(R.size()+1>K){
         it=prev(R.end(),1);
         RC.insert(*it);
         zr-=*it;
         R.erase(it);
      }
   }
   res=max(res,zr-zl);
   res=max(res,zl-zr);
   //cout<<res<<endl;
   for(int i=2;i<N;i++){
      it=R.find(niz[i]);
      LC.insert(niz[i]);
      if(it==R.end()){
         RC.erase(niz[i]);
      }
      else{
         zr-=*it;
         R.erase(it);
         if(RC.size()!=0){
            R.insert(*RC.begin());
            zr+=*RC.begin();
            RC.erase(RC.begin());
         }
         else{
            L.insert(*prev(LC.end(),1));
            zl+=*prev(LC.end(),1);
            LC.erase(prev(LC.end(),1));
         }
      }
      while(LC.size()){
         if(*L.begin()>=*prev(LC.end(),1))
            break;
         it=prev(LC.end(),1);
         L.insert(*it);
         zl+=*it;
         LC.erase(it);
         it=L.begin();
         LC.insert(*it);
         zl-=*it;
         L.erase(it);
      }
      while(RC.size()){
         if(*prev(R.end(),1)<=*RC.begin())
            break;
         it=RC.begin();
         R.insert(*it);
         zr+=*it;
         RC.erase(it);
         it=prev(R.end(),1);
         RC.insert(*it);
         zr-=*it;
         R.erase(it);
      }
      while(L.size()>1 and RC.size()>0){
         if(*L.begin()>=(-*RC.begin()))
            break;
         it=L.begin();
         LC.insert(*it);
         zl-=*it;
         L.erase(it);
         it=RC.begin();
         R.insert(*it);
         zr+=*it;
         RC.erase(it);
      }
      while(R.size()>1 and LC.size()>0){
         if(*prev(LC.end(),1)<=(-*prev(R.end(),1)))
            break;
         it=prev(R.end(),1);
         RC.insert(*it);
         R.erase(it);
         zr-=*it;
         it=prev(LC.end(),1);
         L.insert(*it);
         zl+=*it;
         LC.erase(it);
      }
      //cout<<i<<": "<<zl-zr<<endl;
      res=max(res,zr-zl);
      res=max(res,zl-zr);
   }
   return;
}
int main(){
   res=-9e18;
   cin>>N>>K;
   for(int i=1;i<=N;i++)
      cin>>niz[i];
   izracunaj();
   for(int i=1;i<=N/2;i++)
      swap(niz[i],niz[N-i+1]);
   izracunaj();
   cout<<res<<endl;
}