**C. George and Job

C. George and Job

The new ITone 6 has been released recently and George got really keen to buy it. Unfortunately, he didn't have enough money, so George was going to work as a programmer. Now he faced the following problem at the work.

Given a sequence of n integers p1, p2, ..., pn. You are to choose k pairs of integers:

[l1, r1], [l2, r2], ..., [lk, rk] (1 ≤ l1 ≤ r1 < l2 ≤ r2 < ... < lk ≤ rk ≤ n; ri - li + 1 = m), 

in such a way that the value of sum  is maximal possible. Help George to cope with the task.

Input

The first line contains three integers n, m and k (1 ≤ (m × k) ≤ n ≤ 5000). The second line contains n integers p1, p2, ..., pn(0 ≤ pi ≤ 109).

Output

Print an integer in a single line — the maximum possible value of sum.

Examples

input

5 2 1
1 2 3 4 5

output

9

input

7 1 3
2 10 7 18 5 33 0

output

61

----------------------------------------------EDITORIAL--------------------------------------------------------

JUST FIX STARTING POINTS   IF WE ARE CONSIDERING A POINT AS A NEW STARTING POINT THAN GO TO M INDEX FORWARD , ELSE SHIFT TO NEXT INDEX ....

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

lli dp[5010][5010];

lli n,m,k;

lli arr[100000];

lli fs[100000];

lli solve(int start,int cov)

 {

   if(dp[start][cov]!=-1) return dp[start][cov];

    else if(cov==k) return 0; 

    else if(start>n)

   {

    return INT_MIN;

     

} 

   else

   {

    // cout<<start<<endl;

    lli ret=0;

        if(start+m-1<=n)

           {

           ret=solve(start+m,cov+1)+fs[start+m-1]-fs[start-1];

   }

    ret=max(ret,solve(start+1,cov));

    dp[start][cov]=ret;

    return ret;

  }

 }

int main()

 {

   cin>>n>>m>>k;

   memset(dp,-1,sizeof dp);

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

{

cin>>arr[i];

fs[i]=fs[i-1]+arr[i];

// cout<<fs[i]<<endl;

}

    lli ans=solve(1,0);

     cout<<ans<<endl;

 }