#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 100, K = 220, inF = N * 10000;
int n, k, a[N], dp[N][K][4][2];
int f[4], g[4];
void _max(int &a, int b) { a = max(a, b); }
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  for (int i = 0; i < 4; i++) f[i] = i >> 1, g[i] = f[i] | 2;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 0; i < N; i++)
    for (int j = 1; j < K; j++)
      for (int mask = 0; mask < 8; mask++) dp[i][j][mask >> 1][mask & 1] = -inF;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= k; j++)
      for (int mask = 0; mask < 4; mask++) {
        int z = (mask >> 1 ? 1 : -1) + (mask & 1 ? -1 : +1);
        if (j == 1)
          z = (mask & 1 ? -1 : +1);
        else if (j == k)
          z = (mask >> 1 ? 1 : -1);
        int add = z * a[i];
        dp[i][j][mask][1] = dp[i - 1][j][mask][1];
        _max(dp[i][j][mask][1], add + dp[i - 1][j][mask][0]);
        _max(dp[i][j][mask][1], dp[i - 1][j - 1][f[mask]][1] + add);
        _max(dp[i][j][mask][1], dp[i - 1][j - 1][g[mask]][1] + add);
        dp[i][j][mask][0] = dp[i - 1][j][mask][0] + add;
        _max(dp[i][j][mask][0], dp[i - 1][j - 1][f[mask]][1] + add);
        _max(dp[i][j][mask][0], dp[i - 1][j - 1][g[mask]][1] + add);
      }
  int ans = 0;
  for (int mask = 0; mask < 4; mask++) _max(ans, dp[n][k][mask][1]);
  cout << ans;
  return 0;
}
