#include<bits/stdc++.h>
using namespace std;
#define MAXN 20007
#define ll long long
ll a[MAXN];

int maxsumk(int l, int r, int k, int n)
{
    vector<ll>v;
    for(int i=l;i<=r;i++)
    {
        v.push_back(abs(a[i]));
        //cerr<<abs(a[i])<<" ";
    }
    //cerr<<endl;
    ll sum=0;
    sort(v.begin(),v.end(),greater<int>());
    for(int i=0;i<k;i++)
    {
        sum+=v[i];
    }
    return sum;
}
int solve(int n,int k)
{
    if(k==n)
    {
        ll sum=0;
        for(int i=1;i<n-1;i++)
        {
            sum+=abs(a[i]);
        }
        sum+=max(a[0]-a[n-1],a[n-1]-a[0]);
        cout<<sum<<endl;
        return 0;
    }
    else
    {
        vector<ll>minileft,miniright;
        vector<ll>maxileft,maxiright;
        maxileft.push_back(a[0]);
        minileft.push_back(a[0]);
        for(int i=1;i<n;i++)
        {
            maxileft.push_back(max(maxileft[i-1],a[i]));
            minileft.push_back(min(minileft[i-1],a[i]));
        }
        maxiright.push_back(a[n-1]);
        miniright.push_back(a[n-1]);
        for(int i=n-2;i>=0;i--)
        {
            maxiright.push_back(max(maxiright[n-i-1-1],a[i]));
            miniright.push_back(min(miniright[n-i-1-1],a[i]));
        }
        ll r1,r2;
        vector<ll>v;
        for(int i=0;i<n-k;i++)
        {
            for(int j=i+k-1;j<n;j++)
            {
                //cerr<<i<<" "<<j<<" "<<maxsumk(i+1,j-1,k-2,n)<<endl;
                r1=max(minileft[i]-maxiright[n-1-j],maxiright[n-1-j]-minileft[i]);
                r2=max(maxileft[i]-miniright[n-1-j],miniright[n-1-j]-maxileft[i]);
                v.push_back((r1,r2)+maxsumk(i+1,j-1,k-2,n));
            }
        }
        cout<<*max_element(v.begin(),v.end())<<endl;
        return 0;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t=1;
    int n,k;
    //cin>>t;
    for(int i=0;i<t;i++)
    {
        cin>>n>>k;
        for(int j=0;j<n;j++)
        {
            cin>>a[j];
        }
        solve(n,k);
    }
}