#include <bits/stdc++.h>
using namespace std;
void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.first << ' ' << p.second << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}
#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define MOD 1000000007
#define zeros(x) x&(x-1)^x
#define fi first
#define se second
#define NMAX 10005
const long double PI = acos(-1);

ll dp[NMAX][2], s, dp2[NMAX][2], n, k;
int v[NMAX];

int main(){
  ios::sync_with_stdio(false);
  freopen("ferma.in","r",stdin);
  freopen("ferma.out","w",stdout);

  cin >> n >> k;
  for (int i=1;i<=n;i++){
  	cin >> v[i];
  	s += v[i];
  }


  for (int i=1;i<=k;i++){
  	dp[i][0] = dp[i][1] = -1e18;
  	dp2[i][0] = dp2[i][1] = 1e18;
  }

  for (int i=1;i<=n;i++){
  	for (int j=k;j>=1;j--){
  		dp[j][0] = max(dp[j][0], dp[j][1]);
  		dp[j][1] = max({dp[j-1][0] + v[i], dp[j][1] + v[i], dp[j-1][1] + v[i]});
  	}
  }

	for (int i=1;i<=n;i++){
  	for (int j=k;j>=1;j--){
  		dp2[j][0] = min(dp2[j][0], dp2[j][1]);
  		dp2[j][1] = min({dp2[j-1][0] + v[i], dp2[j][1] + v[i], dp2[j-1][1] + v[i]});
  	}
  }

  cout << max(s - min(dp2[k][0], dp2[k][1]), max(dp[k][0], dp[k][1])) << '\n';

  return 0;
}