#include <bits/stdc++.h>
using namespace std;
int f[30010][210][2][2][2], n, k, a[30010], ans;
int mx(int x, int y) { return (x > y) ? x : y; }
void upd(int &x, int y) { x = mx(x, y); }
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  memset(f, 0xcf, sizeof(f));
  ans = f[0][0][0][0][0];
  for (int i = 0; i <= n; i++) {
    for (int d1 = 0; d1 < 2; d1++)
      for (int d2 = 0; d2 < 2; d2++) f[i][0][d1][d2][1] = 0;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= min(n, k); j++) {
      int t = 1 + (j > 1 && j < min(n, k));
      upd(f[i][j][0][0][0], f[i - 1][j - 1][0][1][1] - t * a[i]);
      upd(f[i][j][0][0][0], f[i - 1][j - 1][1][1][1] - t * a[i]);
      upd(f[i][j][0][0][0], f[i - 1][j][0][0][0] - t * a[i]);
      upd(f[i][j][0][1][0], f[i - 1][j - 1][0][1][1] + ((j == 1) ? a[i] : 0) +
                                ((j == min(n, k)) ? -a[i] : 0));
      upd(f[i][j][0][1][0], f[i - 1][j - 1][1][1][1] + ((j == 1) ? a[i] : 0) +
                                ((j == min(n, k)) ? -a[i] : 0));
      upd(f[i][j][0][1][0], f[i - 1][j][0][1][0] + ((j == 1) ? a[i] : 0) +
                                ((j == min(n, k)) ? -a[i] : 0));
      upd(f[i][j][1][0][0], f[i - 1][j - 1][0][0][1] + ((j == 1) ? -a[i] : 0) +
                                ((j == min(n, k)) ? a[i] : 0));
      upd(f[i][j][1][0][0], f[i - 1][j - 1][1][0][1] + ((j == 1) ? -a[i] : 0) +
                                ((j == min(n, k)) ? a[i] : 0));
      upd(f[i][j][1][0][0], f[i - 1][j][1][0][0] + ((j == 1) ? -a[i] : 0) +
                                ((j == min(n, k)) ? a[i] : 0));
      upd(f[i][j][1][1][0], f[i - 1][j - 1][0][0][1] + t * a[i]);
      upd(f[i][j][1][1][0], f[i - 1][j - 1][1][0][1] + t * a[i]);
      upd(f[i][j][1][1][0], f[i - 1][j][1][1][0] + t * a[i]);
      for (int d1 = 0; d1 < 2; d1++)
        for (int d2 = 0; d2 < 2; d2++) {
          upd(f[i][j][d1][d2][1], f[i][j][d1][d2][0]);
          upd(f[i][j][d1][d2][1], f[i - 1][j][d1][d2][1]);
        }
      if (j == min(n, k)) {
        for (int d1 = 0; d1 < 2; d1++)
          for (int d2 = 0; d2 < 2; d2++) upd(ans, f[i][j][d1][d2][1]);
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}
