Flame Thrower

Poe the Penguin wants to hasten Global Warming (so that he can stay in the water all day long). Therefore. He is going to burn down the trees in Barr the Bear's orchards.

Barr the Bear's orchard contains a row of N trees, labelled from 1 to N from left to right. Poe the Penguin has a flamethrower. This flamethrower can destory a consecutive sequence of at most K trees.

Poe the Penguin wants to cause as much damage as possible. He knows the cost of planting each tree. Poe the Penguin wants to aim his flamethrower in such a way that the sum of costs of trees he destroys is as high as possible. He wonders what this cost is.


The first line contains two integers, N and K.

The following line contains N positive integers. The ith integer denotes the cost of the tree with label i.

You can assume that 1 ≤ KN ≤ 1000.


Output the maximum cost of the trees Poe the Penguin can damage..

Sample Input

6 3
5 8 9 2 4 1

Sample Output


Sample Explanation

Destroying Trees 1 to 3 cost 5+8+9 = 22. (Maximum Cost)

Destroying Trees 2 to 4 cost 8+9+2 = 19.

Destroying Trees 3 to 5 cost 9+2+4 = 15.

Destroying Trees 4 to 6 cost 2+4+1 = 7.

Submitting to 'Flame Thrower'

You're not logged in! Click here to login

Submitting .cpp to 'Flame Thrower'

You're not logged in! Click here to login

Compile Errors

Time Limit: 1 Seconds
Memory Limit: 128MB
No. of ACs: 256
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 100
2 0