#include <bits/stdc++.h>
using namespace std;
int a[200000], f[30001][201][2][2][2], n, k;
int cs(int x, int y, int z, int q) {
  int p;
  if (q == k || q == 1) {
    if (y == 0)
      return x;
    else
      return -x;
  }
  if (y == z)
    return 0;
  else if (y == 0)
    return x * 2;
  else
    return -2 * x;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= k; j++)
      for (int znl = 0; znl <= 1; znl++)
        for (int znp = 0; znp <= 1; znp++)
          for (int op = 0; op <= 1; op++) f[i][j][znp][znl][op] = -1000000000;
  f[0][0][0][1][0] = 0;
  f[0][0][1][0][0] = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j <= k; j++)
      for (int znl = 0; znl <= 1; znl++)
        for (int znp = 0; znp <= 1; znp++)
          for (int op = 0; op <= 1; op++)
            if (f[i][j][znl][znp][op] != -1000000000) {
              if (op == 0) {
                f[i + 1][j][znl][znp][op] =
                    max(f[i + 1][j][znl][znp][op], f[i][j][znl][znp][op]);
                if (j < k)
                  f[i + 1][j + 1][znl][znp][1] = max(
                      f[i + 1][j + 1][znl][znp][1],
                      f[i][j][znl][znp][op] + cs(a[i + 1], znl, znp, j + 1));
              } else {
                f[i + 1][j][znl][znp][op] =
                    max(f[i + 1][j][znl][znp][op],
                        f[i][j][znl][znp][op] + cs(a[i + 1], znl, znp, j));
                for (int to = 0; to <= 1; to++) {
                  f[i + 1][j][znp][to][0] =
                      max(f[i + 1][j][znp][to][0], f[i][j][znl][znp][op]);
                  if (j < k)
                    f[i + 1][j + 1][znp][to][1] = max(
                        f[i + 1][j + 1][znp][to][1],
                        f[i][j][znl][znp][op] + cs(a[i + 1], znp, to, j + 1));
                }
              }
            }
  int mx = -1000000000;
  for (int i = 0; i <= n; i++)
    for (int znl = 0; znl <= 1; znl++)
      for (int znp = 0; znp <= 1; znp++)
        for (int op = 0; op <= 1; op++)
          if (f[i][k][znl][znp][op] > mx) mx = f[i][k][znl][znp][op];
  cout << mx << "\n";
  return 0;
}
