#include <bits/stdc++.h>
using namespace std;
vector<int> nums;
int dp[30100][210][2][2][2];
bool mrk[30100][210][2][2][2];
int n, k;
int bestB(int p, int s, int ls, int ns, int fst) {
  if (s == k) return 0;
  if (mrk[p][s][ls == 1][ns == 1][fst]) return dp[p][s][ls == 1][ns == 1][fst];
  mrk[p][s][ls == 1][ns == 1][fst] = 1;
  int rs = ns;
  if (s) rs -= ls;
  if (s == k - 1) rs -= ns;
  rs *= nums[p];
  int ret =
      rs + max(bestB(p + 1, s + 1, ns, 1, 1), bestB(p + 1, s + 1, ns, -1, 1));
  if (n - p > k - s) {
    if (fst) ret = max(ret, bestB(p + 1, s, ls, ns, 1));
    ret = max(ret, rs + bestB(p + 1, s, ls, ns, 0));
  }
  return dp[p][s][ls == 1][ns == 1][fst] = ret;
}
int main(void) {
  cin >> n >> k;
  int aux;
  for (int i = 0; i < n; i++) {
    cin >> aux;
    nums.push_back(aux);
  }
  int ret = bestB(0, 0, 1, 1, 1);
  ret = max(ret, bestB(0, 0, 1, -1, 1));
  ret = max(ret, bestB(0, 0, -1, 1, 1));
  ret = max(ret, bestB(0, 0, -1, -1, 1));
  cout << ret << endl;
}
