#include <bits/stdc++.h>
using namespace std;
inline int max(int a, int b) { return a < b ? b : a; }
inline int min(int a, int b) { return a > b ? b : a; }
inline long long max(long long a, long long b) { return a < b ? b : a; }
inline long long min(long long a, long long b) { return a > b ? b : a; }
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
const long long INF = 1e18;
long long dp[205][2][2][2][2];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int cur = 0;
  for (int i = 0; i < m + 3; ++i)
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 2; ++k)
        for (int l = 0; l < 2; ++l) dp[i][j][k][l][cur] = -INF;
  while (n--) {
    long long zz;
    int nx = cur ^ 1;
    scanf("%lld", &zz);
    for (int i = 0; i < m + 3; ++i)
      for (int j = 0; j < 2; ++j)
        for (int k = 0; k < 2; ++k)
          for (int l = 0; l < 2; ++l) dp[i][j][k][l][nx] = -INF;
    for (int i = 0; i < m + 1; ++i)
      for (int j = 0; j < 2; ++j)
        for (int k = 0; k < 2; ++k)
          for (int l = 0; l < 2; ++l)
            if (dp[i][j][k][l][cur] > -INF) {
              if (l == 0) {
                long long x1 = dp[i][j][k][l][cur], y1 = 0;
                if (i == 0) {
                  y1 += (-(2 * k - 1) * zz);
                } else if (i == m - 1) {
                  y1 += (2 * j - 1) * zz;
                } else {
                  y1 += (2 * j - 2 * k) * zz;
                }
                dp[i][j][k][l][nx] = max(dp[i][j][k][l][nx], x1 + y1);
                if (i == m && l == 1) printf("%d %d %d %d\n", i, j, k, l);
              } else {
                dp[i][j][k][l][nx] =
                    max(dp[i][j][k][l][nx], dp[i][j][k][l][cur]);
                if (i == m - 1) {
                  long long x1 = dp[i][j][k][l][cur] + (2 * k - 1) * zz;
                  dp[i][k][0][0][nx] = max(dp[i][k][0][0][nx], x1);
                } else {
                  long long x1 = dp[i][j][k][l][cur] + (2 * k - 1) * zz;
                  dp[i][k][0][0][nx] = max(dp[i][k][0][0][nx], x1 + zz);
                  dp[i][k][1][0][nx] = max(dp[i][k][1][0][nx], x1 - zz);
                }
              }
            }
    dp[0][0][0][0][nx] = max(dp[0][0][0][0][nx], zz);
    dp[0][0][1][0][nx] = max(dp[0][0][1][0][nx], -zz);
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < 2; ++j)
        for (int k = 0; k < 2; ++k)
          dp[i + 1][j][k][1][nx] =
              max(dp[i + 1][j][k][1][nx], dp[i][j][k][0][nx]);
    cur = nx;
  }
  long long ans = 0;
  for (int j = 0; j < 2; ++j)
    for (int k = 0; k < 2; ++k) ans = max(ans, dp[m][j][k][1][cur]);
  printf("%lld\n", ans);
  return 0;
}
