#include <iostream> #include <vector> #include <map> #include <string> #include <algorithm> #include <cassert> #include <cstring> #include <stack> #include <set> #include <cmath> #include <queue> #include <iomanip> using namespace std; const int N = 2005; // f[i][j][k] là tổng lớn nhất khi ta xét vị trí i đang ở group j và group j đó nếu = 0 group đang đóng và ngược lại; long long f[N][N][2]; int n , m; int a[N]; int main(){ cin >> n >> m; for(int i = 1; i <= n ;i++){ cin >> a[i]; } const long long NEG = -(1LL << 60); for(int i = 0 ; i <= n ; i++){ for(int j = 0 ; j <= m ; j++){ f[i][j][0] = f[i][j][1] = NEG; } } f[0][0][0] = 0; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j <= m ; j++ ){ if(f[i][j][0] > NEG){ f[i + 1][j][0] = max(f[i + 1][j][0] , f[i][j][0]); if(j < m) f[i + 1][j + 1][1] = max(f[i + 1][j + 1][1] , f[i][j][0] + a[i + 1]); } if(f[i][j][1] > NEG){ f[i + 1][j][0] = max(f[i + 1][j][0] , f[i][j][1]); f[i + 1][j][1] = max(f[i + 1][j][1] , f[i][j][1] + a[i + 1]); } } } cout << max(f[n][m][0], f[n][m][1]); return 0; }