#include <bits/stdc++.h>
using namespace std;
const long long N = 3e4 + 1;
const long long K = 201;
const long long inf = 1e9 + 2;
long long dp[2][K][2][3][3], ar[N];
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, i, j, k, l, num, m;
  cin >> n >> num;
  for (i = 1; i <= n; i++) {
    cin >> ar[i];
  }
  memset(dp, -inf, sizeof(dp));
  dp[0][0][1][1][1] = 0;
  for (i = 0; i <= n; i++) {
    for (j = 0; j <= min(i + 1, num); j++) {
      for (k = 0; k <= 1; k++) {
        for (l = 0; l <= 2; l++) {
          for (m = 0; m <= 2; m++) {
            dp[1 - (i & 1)][j][k][l][m] = -inf;
          }
        }
      }
    }
    for (j = 0; j <= min(i, num); j++) {
      for (k = 0; k <= 1; k++) {
        for (l = 0; l <= 2; l++) {
          for (m = 0; m <= 2; m++) {
            if (!k && i < n) {
              dp[1 - (i & 1)][j][k][l][m] =
                  max(dp[1 - (i & 1)][j][k][l][m],
                      dp[i & 1][j][k][l][m] + (l + m - 2) * ar[i + 1]);
            }
            if (!k && i > 0) {
              dp[i & 1][j][1][l][m] =
                  max(dp[i & 1][j][1][l][m], dp[i & 1][j][k][l][m]);
            }
            if (k && i < n) {
              dp[1 - (i & 1)][j][1][l][m] =
                  max(dp[1 - (i & 1)][j][1][l][m], dp[i & 1][j][k][l][m]);
            }
            if (k && i < n && j < num) {
              if (j == num - 1) {
                dp[1 - (i & 1)][j + 1][0][2 - m][1] =
                    max(dp[1 - (i & 1)][j + 1][0][2 - m][1],
                        dp[i & 1][j][k][l][m] + (1 - m) * ar[i + 1]);
              } else {
                dp[1 - (i & 1)][j + 1][0][2 - m][0] =
                    max(dp[i & 1][j][k][l][m] + (-m) * ar[i + 1],
                        dp[1 - (i & 1)][j + 1][0][2 - m][0]);
                dp[1 - (i & 1)][j + 1][0][2 - m][1] =
                    max(dp[1 - (i & 1)][j + 1][0][2 - m][1],
                        dp[i & 1][j][k][l][m] + (1 - m) * ar[i + 1]);
                dp[1 - (i & 1)][j + 1][0][2 - m][2] =
                    max(dp[1 - (i & 1)][j + 1][0][2 - m][2],
                        dp[i & 1][j][k][l][m] + (2 - m) * ar[i + 1]);
              }
            }
          }
        }
      }
    }
  }
  cout << max(dp[n & 1][num][1][0][1], dp[n & 1][num][1][2][1]);
}
