#include<bits/stdc++.h>
using namespace std;
long long N,K,a[200005],sol,L,D,sumLa,sumDa,pok,x;
priority_queue<int>QLa,QLb,QDb;
map<int,int>update,kol;
vector<int>vDa;
int main(){
  cin>>N>>K;
  for(int i=1; i<=N; i++)cin>>a[i];
  sol=0;
  if(N==K){

    return 0;
  }
  for(int pon=1; pon<=2; pon++){
    for(int P=1; P<=K-1; P++){
      //cout<<"P : "<<P<<endl;
      QLa.empty();
      vDa.clear();
      update.clear();
      kol.clear();
      L=P;
      D=K-P;
      sumLa=0;
      sumDa=0;
      for(int i=1; i<=L; i++)sumLa+=a[i];
      for(int i=1; i<=L; i++)QLa.push(-a[i]);
      for(int i=L+1; i<=N; i++)vDa.push_back(a[i]);
      for(int i=0; i<vDa.size(); i++)kol[vDa[i]]++;
      sort(vDa.begin(),vDa.end());
      //cout<<"vDa :";
      //for(int i=0; i<vDa.size(); i++)cout<<vDa[i]<<" ";;
      //cout<<endl;
      for(int i=0; i<D; i++)sumDa+=vDa[i];
      //cout<<sumLa<<" "<<sumDa<<endl;
      sol=max(sol,abs(sumLa-sumDa));
      pok=D-1;
      for(int i=L+1; i<=N-D; i++){
        x=a[i];
        QLa.push(-x);
        sumLa+=x;
        sumLa+=QLa.top();
        QLa.pop();
        update[x]++;
        //cout<<"move "<<x<<endl;
        if(x<=vDa[pok] and kol[x]>0){

          while(update[vDa[pok+1]]>0){
              /*
            cout<<update[vDa[pok+1]]<<endl;
            cout<<pok<<" pok"<<endl;
            */
            update[vDa[++pok]]--;
            /*
            cout<<vDa[pok]<<" ";
            cout<<update[vDa[pok]]<<endl;
            */
          }
          //cout<<++pok<<endl;
          sumDa-=x;
          sumDa+=vDa[pok];
        }
        kol[x]--;
        /*
        cout<<pok<<endl;
        cout<<sumLa<<" "<<sumDa<<endl;
        */
        sol=max(sol,abs(sumLa-sumDa));
      }
      for(int i=1; i<=N/2; i++)swap(a[i],a[N-i+1]);
    }
    //cout<<sol<<" sol"<<endl;

  }
  cout<<sol<<endl;
  return 0;
}
/*
5 3
-2 4 3 -7 3
*/