#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int MAXN = 3e4 + 5;
const int MAXK = 205;
const int inf = 1e9;
const int sign[2] = {1, -1};
int nextInt() {
  int ret = 0, d;
  bool negative = false;
  d = getchar();
  if (d == 45) negative = true;
  while (d < 48 || d > 57) {
    d = getchar();
    if (d == 45) negative = true;
  }
  do {
    ret = ret * 10 + d - 48;
    d = getchar();
  } while (d > 47 && d < 58);
  if (negative) return -ret;
  return ret;
}
int n, k, a[MAXN];
int dp[MAXN][MAXK][2][2][2];
int rek(int i, int j, int imam, int sign1, int sign2) {
  if (dp[i][j][imam][sign1][sign2]) return dp[i][j][imam][sign1][sign2];
  if (!j) return 0;
  if (!i) return -inf;
  if (!imam)
    return dp[i][j][imam][sign1][sign2] = max(rek(i - 1, j, 0, sign1, sign2),
                                              rek(i - 1, j, 1, sign1, sign2));
  int add;
  if (j == k) {
    if (sign2)
      add = -a[i];
    else
      add = a[i];
  } else if (j == 1) {
    if (sign1)
      add = a[i];
    else
      add = -a[i];
  } else {
    if (sign1 == sign2)
      add = 0;
    else
      add = a[i] * -sign[sign1] + a[i] * sign[sign2];
  }
  int ret = rek(i - 1, j - 1, 0, sign2, 0);
  ret = max(ret, rek(i - 1, j - 1, 1, sign2, 0));
  ret = max(ret, rek(i - 1, j - 1, 0, sign2, 1));
  ret = max(ret, rek(i - 1, j - 1, 1, sign2, 1));
  ret = max(ret, rek(i - 1, j, 1, sign1, sign2));
  return dp[i][j][imam][sign1][sign2] = ret + add;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  n = nextInt();
  k = nextInt();
  for (int i = 0; i < n; ++i) {
    a[i + 1] = nextInt();
  }
  int sol = -inf;
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j)
      for (int z = 0; z < 2; ++z) sol = max(sol, rek(n, k, i, j, z));
  cout << sol;
}
