#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[402];
int dp[402][51][51][2][2];
void upd(int &a, int b) { a = max(a, b); }
int main() {
  cin >> n >> k;
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= k; j++)
      for (int z = 0; z <= k; z++)
        dp[i][j][z][0][0] = dp[i][j][z][0][1] = dp[i][j][z][1][0] =
            dp[i][j][z][1][1] = -2000000000;
  dp[0][0][0][0][0] = dp[0][0][0][0][1] = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    for (int j = 0; j <= k; j++) {
      for (int z = 0; z <= k; z++) {
        if (z) {
          upd(dp[i][j][z][0][0], dp[i - 1][j][z - 1][0][0]);
          upd(dp[i][j][z][0][0], dp[i - 1][j][z - 1][1][0]);
          upd(dp[i][j][z][0][1], dp[i - 1][j][z - 1][0][1]);
          upd(dp[i][j][z][0][1], dp[i - 1][j][z - 1][1][1]);
        }
        if (z == k) {
          upd(dp[i][j][z][0][0], dp[i - 1][j][z][0][0]);
          upd(dp[i][j][z][0][0], dp[i - 1][j][z][1][0]);
          upd(dp[i][j][z][0][1], dp[i - 1][j][z][0][1]);
          upd(dp[i][j][z][0][1], dp[i - 1][j][z][1][1]);
        }
        if (j == 1) {
          upd(dp[i][j][z][1][0], dp[i - 1][j][z][1][0] - a[i]);
          upd(dp[i][j][z][1][1], dp[i - 1][j][z][1][1] + a[i]);
          upd(dp[i][j][z][1][0], dp[i - 1][j - 1][z][0][1] - a[i]);
          upd(dp[i][j][z][1][0], dp[i - 1][j - 1][z][1][1] - a[i]);
          upd(dp[i][j][z][1][1], dp[i - 1][j - 1][z][0][0] + a[i]);
          upd(dp[i][j][z][1][1], dp[i - 1][j - 1][z][1][0] + a[i]);
        }
        if (j > 1) {
          upd(dp[i][j][z][1][0], dp[i - 1][j][z][1][0] - 2 * a[i]);
          upd(dp[i][j][z][1][1], dp[i - 1][j][z][1][1] + 2 * a[i]);
          upd(dp[i][j][z][1][0], dp[i - 1][j - 1][z][0][1] - 2 * a[i]);
          upd(dp[i][j][z][1][0], dp[i - 1][j - 1][z][1][1] - 2 * a[i]);
          upd(dp[i][j][z][1][1], dp[i - 1][j - 1][z][0][0] + 2 * a[i]);
          upd(dp[i][j][z][1][1], dp[i - 1][j - 1][z][1][0] + 2 * a[i]);
        }
      }
    }
  }
  int ans = -2000000000;
  for (int i = 1; i <= n; i++) {
    int sum = 0, ma = -2000000000, mi = ma;
    for (int j = 1; j < k; j++)
      for (int z = 0; z <= k; z++)
        if (j + 1 + z >= k) {
          upd(ma, dp[i - 1][j][z][1][0]);
          upd(ma, dp[i - 1][j][z][0][0]);
          upd(mi, dp[i - 1][j][z][1][1]);
          upd(mi, dp[i - 1][j][z][0][1]);
        }
    for (int j = i; j <= n; j++) {
      ma += a[j];
      mi -= a[j];
      upd(ans, ma);
      upd(ans, mi);
    }
  }
  cout << ans << endl;
}
