#include <bits/stdc++.h> #define endl "\n" using namespace std; const int MAXN = 2000+5; int n,k; long long a[MAXN]; void read() { cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i]; } long long dp[MAXN][MAXN][2]; void solve() { 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][0],dp[i-1][j][1]) + a[i]; } } /*for(int j = 1; j <= k; j++) { for(int i = 1; i <= n; i++) { cout << "{ " << dp[i][j][0] << " - " << dp[i][j][1] << " } "; } cout << endl; }*/ cout << max(dp[n][k][1],dp[n][k][0]) << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); read(); solve(); return 0; }