#include <bits/stdc++.h>
using namespace std;
void upd(int& a, const int& b) { a = max(a, b); }
const int maxk = 207, inf = 1e9 + 79;
int dp[2][maxk][2][3][3];
int sign(int x, int flag) {
  if (flag == 0) return -x;
  if (flag == 1) return x;
  if (flag == 2) return 0;
}
void clear_layer(int x) {
  for (int i = 0; i < maxk; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 3; k++)
        for (int l = 0; l < 3; l++) dp[x][i][j][k][l] = -inf;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> v(n + 1);
  for (int i = 1; i <= n; i++) cin >> v[i];
  clear_layer(0);
  for (int i = 1; i <= n; i++) {
    clear_layer(i & 1);
    int b1 = i & 1, b0 = (i - 1) & 1;
    for (int s2 = 0; s2 < 2; s2++) upd(dp[b1][1][1][2][s2], sign(v[i], s2));
    for (int cuts = 0; cuts <= k; cuts++) {
      for (int s1 = 0; s1 < 3; s1++)
        for (int s2 = 0; s2 < 3; s2++) {
          upd(dp[b1][cuts][1][s1][s2],
              dp[b0][cuts][1][s1][s2] + sign(v[i], s1) + sign(v[i], s2));
          upd(dp[b1][cuts][0][s1][s2], dp[b0][cuts][1][s1][s2]);
          upd(dp[b1][cuts][0][s1][s2], dp[b0][cuts][0][s1][s2]);
        }
      if (cuts == k) continue;
      for (int op = 0; op < 2; op++)
        for (int s1 = 0; s1 < 3; s1++)
          for (int s2 = 0; s2 < 2; s2++) {
            for (int nws1 = 0; nws1 < 2; nws1++) {
              if (nws1 == s2) continue;
              int l = 0, r = 2;
              if (cuts + 1 == k) l = 2, r = 3;
              for (int nws2 = l; nws2 < r; nws2++) {
                upd(dp[b1][cuts + 1][1][nws1][nws2], dp[b0][cuts][op][s1][s2] +
                                                         sign(v[i], nws1) +
                                                         sign(v[i], nws2));
              }
            }
          }
    }
  }
  int ans = 0;
  for (int op = 0; op < 2; op++)
    for (int s1 = 0; s1 < 2; s1++) upd(ans, dp[n & 1][k][op][s1][2]);
  cout << ans << "\n";
  return 0;
}
