#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30004, INF = 1000000000;
int n, k;
int v[MAXN];
int pd[4][MAXN][202];
int res[4][MAXN][202];
int solve(int x, int p, int y) {
  if (y <= 0) return -INF;
  if (p >= n) return -INF;
  if (pd[x][p][y] == -1) {
    int ans = -INF;
    if (y == 1) {
      if (x == 1) {
        ans = v[p] + max(0, solve(x, p + 1, y));
      } else if (x == 3) {
        ans = -v[p] + max(0, solve(x, p + 1, y));
      } else {
        ans = solve(x, p + 1, y);
        ans = max(ans, solve((x + 1) % 4, p + 1, y));
      }
    } else if (y == k) {
      if (x == 1) {
        ans = solve(1, p + 1, y) + v[p];
        ans = max(ans, solve(2, p + 1, y - 1) + v[p]);
        ans = max(ans, solve(3, p + 1, y - 1) + v[p]);
      } else if (x == 3) {
        ans = solve(3, p + 1, y) - v[p];
        ans = max(ans, solve(0, p + 1, y - 1) - v[p]);
        ans = max(ans, solve(1, p + 1, y - 1) - v[p]);
      } else {
        ans = solve(x, p + 1, y);
        ans = max(ans, solve((x + 1) % 4, p + 1, y));
      }
    } else {
      if (x == 1) {
        ans = solve(1, p + 1, y) + 2 * v[p];
        ans = max(ans, solve(2, p + 1, y - 1) + 2 * v[p]);
        ans = max(ans, solve(3, p + 1, y - 1) + 2 * v[p]);
      } else if (x == 3) {
        ans = solve(3, p + 1, y) - 2 * v[p];
        ans = max(ans, solve(0, p + 1, y - 1) - 2 * v[p]);
        ans = max(ans, solve(1, p + 1, y - 1) - 2 * v[p]);
      } else {
        ans = solve(x, p + 1, y);
        ans = max(ans, solve((x + 1) % 4, p + 1, y));
        ans = max(ans, solve(x, p + 1, y - 1));
        ans = max(ans, solve((x + 1) % 4, p + 1, y - 1));
      }
    }
    pd[x][p][y] = 1;
    res[x][p][y] = ans;
  }
  return res[x][p][y];
}
int main() {
  while (cin >> n >> k) {
    memset(pd, -1, sizeof pd);
    for (int i = 0; i < n; ++i) cin >> v[i];
    int ans = 0;
    for (int i = 0; i < 4; ++i) ans = max(solve(i, 0, k), ans);
    cout << ans << endl;
  }
}
