//WA #include #include #include using namespace std; using namespace atcoder; using ll = long long; //#define endl "\n"; const long long INF = 1e9; int main(){ ll N, K; cin >> N >> K; vector A(N); for(int i = 0; i < N; i++) cin >> A[i]; //N/2> dp(K + 1, vector(2, -INF)); dp[0][0] = 0; for(int i = 0; i < N; i++){ vector> tmp(K + 1, vector(2, -INF)); for(int j = 0; j <= K; j++){ //選ぶ if(j + 1 <= K) tmp[j + 1][1] = max(tmp[j + 1][1], dp[j][0] + A[i]); //選ばない tmp[j][0] = max(tmp[j][0], dp[j][0]); tmp[j][0] = max(tmp[j][0], dp[j][1]); } swap(dp, tmp); } ll ans = max(dp[K][0], dp[K][1]); cout << ans << endl; return 0; }