POJ 3661

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 10010
using namespace std;

int n,m;
int dis[M],dp[M][505];

int main(){
	while(~scanf("%d%d",&n,&m)){
		for(int i=1;i<=n;i++)
			scanf("%d",&dis[i]);
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m&&j<=i;j++)
				dp[i][j]=dp[i-1][j-1]+dis[i];			
			dp[i][0]=dp[i-1][0];
			for(int j=1;j<=m&&i-j>=j;j++)
				dp[i][0]=max(dp[i-j][j],dp[i][0]);
		}
		printf("%d\n",dp[n][0]);
	}
	return 0;
}