#include <bits/stdc++.h>
using namespace std;
const int maxn = 30009;
const int maxm = 209;
int f[maxn][maxm][2];
int g[maxn][maxm][2];
int a[maxn], n, m;
inline int read() {
  char ch = getchar();
  int x = 0, f = 1;
  while (ch < '0' || '9' < ch) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  memset(f, 0xc0, sizeof f);
  memset(g, 0xc0, sizeof g);
  f[0][0][0] = f[0][0][1] = 0;
  g[0][0][0] = g[0][0][1] = 0;
  for (int i = 1; i <= n; i++) {
    g[i][0][0] = g[i - 1][0][0];
    g[i][0][1] = g[i - 1][0][1];
    for (int j = 1; j <= i && j <= m; j++) {
      if (1 < j && j < m) a[i] *= 2;
      f[i][j][0] = max(f[i - 1][j][0], g[i - 1][j - 1][1]) + a[i];
      f[i][j][1] = max(f[i - 1][j][1], g[i - 1][j - 1][0]) - a[i];
      g[i][j][0] = max(f[i][j][0], g[i - 1][j][0]);
      g[i][j][1] = max(f[i][j][1], g[i - 1][j][1]);
      if (1 < j && j < m) {
        a[i] /= 2;
        g[i][j][0] = max(g[i][j][0], g[i - 1][j - 1][0]);
        g[i][j][1] = max(g[i][j][1], g[i - 1][j - 1][1]);
      }
    }
  }
  printf("%d\n", max(g[n][m][0], g[n][m][1]));
  return 0;
}
