#include <bits/stdc++.h>
using namespace std;
const int N = 30005;
int n, m, f[N][205][4], a[N];
int main() {
  scanf("%d%d", &n, &m);
  memset(f, -0x3f, sizeof(f));
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 0; i <= n; i++)
    for (int j = 0; j < 4; j++) f[i][0][j] = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      int x = 1;
      if (j != 1 && j != m) x++;
      if (x == 2)
        f[i][j][1] = f[i - 1][j - 1][1], f[i][j][3] = f[i - 1][j - 1][3];
      f[i][j][1] = max(
          f[i][j][1],
          max(f[i - 1][j][1],
              f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j - 1][3]) - x * a[i]));
      f[i][j][3] = max(
          f[i][j][3],
          max(f[i - 1][j][3],
              f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][1]) + x * a[i]));
    }
  printf("%d", max(f[n][m][1], f[n][m][3]));
  return 0;
}
