N个整数组成的序列a[1],a[2],a[3],…,a[n]，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。如果M >= N个数中正数的个数，那么输出所有正数的和。

例如：-2 11 -4 13 -5 6 -2，分为2段，11 -4 13一段，6一段，和为26。

Input

第1行：2个数N和M，中间用空格分隔。N为整数的个数，M为划分为多少段。（2 <= N , M <= 5000)

第2 - N+1行：N个整数 (-10^9 <= a[i] <= 10^9)

Output

输出这个最大和

Input示例

7 2

-2

11

-4

13

-5

6

-2

Output示例

26
【分析】dp[j][i]表示从1~i分成j份获得的最大值。

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define met(a,b) memset(a,b,sizeof a)

#define pb push_back

#define mp make_pair

#define rep(i,l,r) for(int i=(l);i<=(r);++i)

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N = 1e6+;;

const int M = ;

const int mod = 1e9+;

const int mo=;

const double pi= acos(-1.0);

typedef pair<int,int>pii;

int n,m;

int a[N];

ll dp[][N];

int main(){

    scanf("%d%d",&n,&m);

        met(dp,);

        ll sum=;

        int cnt=;

        for(int i=;i<=n;i++){

            scanf("%d",&a[i]);

            if(a[i]>)sum+=a[i],cnt++;

        }

        if(m>=cnt)return *printf("%lld\n",sum);

        int now=;

        for(int i=;i<=m;i++){

            ll mx=dp[now^][i-];

            dp[now][i]=mx+a[i];

            for(int j=i+;j<=n-m+i;j++){

                mx=max(mx,dp[now^][j-]);

                dp[now][j]=max(mx,dp[now][j-])+a[j];

            }

            now^=;

        }

        now^=;

        ll ans=-;

        for(int i=m;i<=n;i++)ans=max(ans,dp[now][i]);

        printf("%lld\n",ans);

    return ;

}