#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

const int N = 3e4 + 3;
const int K = 200 + 3;
const int MAX = 1e6 + 3;
const ll INF = 1e18;

pair<bool, ll> dp[N][K][2];
ll a[N];
int n, k;

ll solve(int in, int ik, bool pos = false){
    if(ik == k){
        if(in == n) return 0;
        return -INF;
    }
    if(ik == k - 1 && (k & 1)){
        if(in > n) return -INF;
        return 0;
    }

    auto &[solved, ans] = dp[in][ik][pos];
    if(solved)
        return ans;

    solved = true;
    ans = -INF;

    if(ik % 2 == 0){
        if(in + 2 > n)
            return ans = -INF;

        if(!pos) ans = -a[in] + solve(in + 1, ik + 1, true);
        check_max(ans, a[in] - a[in + 1] + solve(in + 2, ik + 2));
        check_max(ans, a[in] + solve(in + 1, ik, true));
        return ans;
    }

    if(in == n)
        return ans = -INF;

    ans = a[in] + solve(in + 1, ik + 1);
    check_max(ans, a[in] + solve(in + 1, ik));

    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

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

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

    cout << solve(0, 0) << "\n";
}