#include <iostream>
#include <fstream>

using namespace std;

const int MAXN = 3e4;
const int MAXK = 200;
const int64_t inf = 1e15;

int n, k;
int a[MAXN];

int64_t dp[MAXN+5][2];

int main()
{
    ifstream cin("monkeys.in");
    ofstream cout("monkeys.out");

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    if(k==1)
    {
        cout << "0" << '\n';
        return 0;
    }

    for(int iter = 0;iter<k/2;iter++)
    {
        int64_t opt1 = -inf, opt2 = -inf;

        for(int i = 0;i<n;i++)
            dp[i][iter&1] = -inf;

        if(iter==0)
        {
            opt1 = 0 + a[0];
            opt2 = 0 - a[0];
        }

        for(int i = 1;i<n;i++)
        {
            //1. dp[j] + [j+1...i] - a[i]
            //2. dp[j] - a[j+1] + [j+2...i-1] + a[i]

            dp[i][iter&1] = max(opt1-a[i], opt2+a[i]);

            opt1 = max(opt1+a[i], dp[i-1][(iter&1)^1] + a[i]);
            opt2 = max(opt2+a[i], dp[i-1][(iter&1)^1] - a[i]);
        }
    }

    int64_t ans = -inf;
    if(k%2==0)
    {
        ans = dp[n-1][(k/2-1)&1];
    }
    else
    {
        for(int i = 0;i<n;i++)
            ans = max(ans, dp[i][(k/2-1)&1]);
    }

    cout << ans << '\n';
}