VTS c++

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, n) for (int(i) = 0;

  (i) < (n); ++(i))

  #define REP(i, a, b) for (int(i) = (a);

    (i) <= (b); ++i)

    const int INF = 1e9,

      mod = 1e9 + 7;

template < class T >

  inline bool maximize(T & x,

    const T & y) {

    if (x < y) {

      x = y;

      return 1;

    }

    return 0;

  }

typedef long long ll;

typedef double db;

const int N = 2e3 + 5;

ll dp[N][N][3], a[N];

int n, k;

void readip() {

  cin >> n >> k;

  FOR(i, n) cin >> a[i];

  memset(dp, -0x3f, sizeof dp);

}

void solve() {

  FOR(i, 3) dp[0][0][i] = 0;

  REP(i, 1, n) {

    FOR(j, i) FOR(t, 3) {

      maximize(dp[i][j][t], dp[i - 1][j][t]);

      ll val = dp[i - 1][j][t];

      if ((t + 1) % 3 == 1) val -= a[i - 1];

      else val += a[i - 1];

      maximize(dp[i][j + 1][(t + 1) % 3], val);

    }

  }

  ll res = -1e18;

  FOR(i, 3) maximize(res, dp[n][3 * k][i]);

  cout << res;

}

int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(0);

  cout.tie(0);

  freopen("b.inp", "r", stdin);

  freopen("b.out", "w", stdout);

  readip();

  solve();

}