#include <bits/stdc++.h> using namespace std; #define int long long constexpr int N = 2005; int dp[N][N][2], a[N]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; } if (n > 2000) { k = min(k, 3LL); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { 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] + a[i], dp[i - 1][j - 1][0] + a[i]); } } cout << max(dp[n][k][0], dp[n][k][1]) << '\n'; return 0; }