shelock-holmes-and-you-1

Sherlock Holmes is your good friend. You are a very good programmer but you also know that Sherlock Holmes has better observing powers. So there is a problem which you two have to solve. Lets see who solves it first.

Given a  sequence of n integers S1,S2,S3,.......,Sn.  You have to chose k windows of size m-1 each (where m is given to you) such that sum of all the elements in these k windows is maximum possible.
Window [l i, r i ] contains all elements from Sl to Sr . Window size ( r i -  l i ) should be equal to m-1 . 

Choose k windows
 [l 1, r 1], [l 2, r 2], [l 3, r 3],......., [l k, r k].                  
   Such that   1 ≤ l 1 ≤ r 1 < l 2 ≤ r 2< ......... <l k ≤r k ≤ n  . (Windows should not overlap).             
 and r i -  l i  =  m - 1

INPUT

First line contains three integers n, m and k (1 ≤ (m × k) ≤ n ≤ 5000). The second line contains n space seperated integers S1,S2,S3,.......,Sn (0 ≤ Si ≤ 10^9)

OUTPUT

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

SAMPLE INPUT
5 2 2
1 7 3 6 5

SAMPLE OUTPUT
21

Explanation

The window size is m-1, that is equal to 1 in this case and we have to select 2 windows. 
Windows corresponding to the answer are [2,3] and [4,5] so sum = 7+3+6+5 = 21.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: