#include <bits/stdc++.h>
using namespace std;
int n, m, v[30010];
int dp[30010][210][8];
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> v[i];
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      for (int k = 0; k < 8; ++k) dp[i][j][k] = -1000000000;
    }
  }
  dp[1][1][0] = 0;
  dp[1][1][1] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m + 1; ++j) {
      for (int k = 0; k < 8; ++k) {
        if (dp[i][j][k] == -1000000000) continue;
        int val = 0;
        int b = 2;
        if (k & 1) b = 0;
        if (j != 1) {
          if ((k >> 1) & 1) {
            val -= v[i];
          } else
            val += v[i];
        }
        if (j != m) {
          if (k & 1) {
            val -= v[i];
          } else
            val += v[i];
        }
        if ((k >> 2) & 1) {
          dp[i + 1][j + 1][0 | b] =
              max(dp[i + 1][j + 1][0 | b], max(dp[i][j][k], dp[i][j][k] + val));
          dp[i + 1][j + 1][1 | b] =
              max(dp[i + 1][j + 1][1 | b], max(dp[i][j][k], dp[i][j][k] + val));
          dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + val);
        } else {
          dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
          dp[i + 1][j][k | 4] = max(dp[i + 1][j][k | 4], dp[i][j][k] + val);
          dp[i + 1][j + 1][0 | b] =
              max(dp[i + 1][j + 1][0 | b], dp[i][j][k] + val);
          dp[i + 1][j + 1][1 | b] =
              max(dp[i + 1][j + 1][1 | b], dp[i][j][k] + val);
        }
      }
    }
  }
  cout << dp[n + 1][m + 1][0];
}
