#include<iostream> #include<cstdio> #include<cmath> #include<string> #include<cstring> #include<algorithm> #include<cctype> #include<queue> using namespace std; #define inf 0xfffffff int a[1000002]; int dp[1000002]; int pre[1000002]; void clear() { memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); memset(pre,0,sizeof(pre)); } int main() { int n,m; while(scanf("%d%d",&m,&n)!=EOF) { int i,j; clear(); for(i=1;i<=n;i++) scanf("%d",&a[i]); long long maxn; for(i=1;i<=m;i++) { maxn=-inf; for(j=i;j<=n;j++) { dp[j]=max(dp[j-1],pre[j-1])+a[j]; //pre[j-1]表示max(dp[i-1][k]) i-1<=k<=j-1 pre[j-1]=maxn; if(dp[j]>maxn) maxn=dp[j]; } } printf("%I64d\n",maxn); } }