#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, x, t;
int f[30003][202][3], g[30003][202][3];
int main() {
  scanf("%d %d", &n, &m);
  for (i = 0; i <= n; ++i)
    for (j = 1; j <= m; ++j)
      f[i][j][0] = f[i][j][1] = g[i][j][0] = g[i][j][1] = -1e9;
  for (i = 1; i <= n; ++i) {
    scanf("%d", &x);
    for (j = 1; j <= m; ++j) {
      if (1 < j && j < m)
        t = x * 2;
      else
        t = x;
      f[i][j][0] = max(f[i - 1][j][0] - t, g[i - 1][j - 1][1] - t);
      f[i][j][1] = max(f[i - 1][j][1] + t, g[i - 1][j - 1][0] + t);
      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) {
        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", max(g[n][m][0], g[n][m][1]));
}
