#include<iostream>
using namespace std;

const int MAXN=3e4, MAXK=200, INF=1e9;

long long dp[MAXN][MAXK+1], pref[MAXN+1];
int a[MAXN];

long long GetSum(int n, int m)
{
    return max(abs(pref[m+1]-pref[n+1]-a[n]), abs(pref[m]-pref[n]-a[m]));
}

long long GetMaxSum(int idx, int n, int k)
{
    if(idx==n && k==0)
    {
        return 0;
    }

    if(k==0)
    {
        return -INF;
    }

    if(idx>=n-1)
    {
        return -INF;
    }

    if(dp[idx][k]!=-1)
    {
        return dp[idx][k];
    }

    long long res=0;
    for(int i=idx+1; i<n; i++)
    {
        res=max(res, GetSum(idx, i)+GetMaxSum(i+1, n, k-2));
    }

    for(int i=idx+1; i<n; i++)
    {
        if(a[i]>a[idx] && i<n-1 && a[i+1]>a[idx])
        {
            continue;
        }

        res=max(res, GetSum(idx, i)+GetMaxSum(i+1, n, k-2));
    }

    return dp[idx][k]=res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    freopen("monkeys.in", "r", stdin);
    freopen("monkeys.out", "w", stdout);

    int n, k;
    cin >> n >> k;

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<=k; j++)
        {
            dp[i][j]=-1;
        }
    }

    pref[0]=0;
    for(int i=0; i<n; i++)
    {
        cin >> a[i];

        pref[i+1]=pref[i]+a[i];
    }

    cout << GetMaxSum(0, n, k) << "\n";

    return 0;
}
/*
10 6
1 2 3 4 5 6 7 8 9 10
*/