#include<bits/stdc++.h> #define x first #define y second using namespace std; using ll = long long; const int maxn = 2100; int N, K, A[maxn]; ll Dp[maxn][maxn][2]; int main() { // freopen("feast.inp", "r", stdin); // freopen("feast.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cin >> N >> K; for (int i = 1; i <= N; ++i) cin >> A[i]; Dp[0][0][0] = 0; for (int i = 1; i <= N; ++i) { Dp[i][0][0] = 0; for (int j = 1; j <= K; ++j) { Dp[i][j][1] = max(Dp[i - 1][j][1], Dp[i - 1][j - 1][0]) + A[i]; Dp[i][j][0] = max(Dp[i - 1][j][1], Dp[i - 1][j][0]); } } cout << max(Dp[N][K][0], Dp[N][K][1]); return 0; }