#include using namespace std; #define INF 1.1e9 #define LINF 1.1e18 #define FOR(i,a,b) for (int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() #define pb push_back #define pf push_front #define fi first #define se second #define BIT(x,n) bitset(x) #define PI 3.14159265358979323846 typedef long long ll; typedef pair P; typedef pair PP; //----------------------------------------------------------------------------- int n,m,w[3010]; int dp[3010][3010][2]; //頂点iまででj個の頂点を使ったときの最大値。kは頂点iを使ったかどうか。 int ans=-INF; int main() { cin.tie(0); ios::sync_with_stdio(false); REP(i,3010) FOR(j,1,3010) dp[i][j][0]=dp[i][j][1]=-INF; cin>>n>>m; REP(i,n) cin>>w[i+1]; // 頂点1を使わない dp[1][0][0]=0; FOR(i,1,n+1) { FOR(j,0,n+1) { // 頂点i+1を使わない dp[i+1][j][0]=max(dp[i+1][j][0],max(dp[i][j][0],dp[i][j][1])); // 頂点i+1を使う dp[i+1][j+1][1]=max(dp[i+1][j+1][1],max(dp[i][j][0],dp[i][j][1]+w[i])); } ans=max(ans,dp[i][m][0]); } ans=dp[n+1][m][0]; // 頂点1=n+1 REP(i,3010) FOR(j,1,3010) dp[i][j][0]=dp[i][j][1]=-INF; // 頂点1を使う。 dp[1][1][1]=0; FOR(i,1,n+1) { FOR(j,1,n+1) { // 頂点iを使わない dp[i+1][j][0]=max(dp[i+1][j][0],max(dp[i][j][0],dp[i][j][1])); // 頂点iを使う dp[i+1][j+1][1]=max(dp[i+1][j+1][1],max(dp[i][j][0],dp[i][j][1]+w[i])); } if(i==n) ans=max(ans,dp[n][m][1]+w[n]); else ans=max(ans,dp[i][m][1]); } /*FOR(i,1,n+1) { REP(j,n+1) cout<<(dp[i][j][0]>=0?dp[i][j][0]:-1)<<' '; cout<<'|'; REP(j,n+1) cout<<(dp[i][j][1]>=0?dp[i][j][1]:-1)<<' '; cout<