#include <bits/stdc++.h> using namespace std; typedef long long llong; const int MAXN = 2e3 + 10; const llong INF = 4e18 + 10; int n, k; llong dp[MAXN][MAXN][2]; int a[MAXN]; void read() { cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> a[i]; } } void solve() { llong ans = -INF; for(int j = 1; j <= k; j++) { for(int i = 1; i <= n; i++) { dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]); dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0]) + a[i]; } ans = max(ans, dp[n][j][0]); ans = max(ans, dp[n][j][1]); } cout << ans << endl; } int main() { read(); solve(); return 0; }