Eat Your Peanuts

You and your friends are at a peanut eating contest. There are N plates on the table in order 1 to N. You are given the number of peanuts in each plate (not all equal).

You need to assign each of your friends one or more plates that are next to each other. You also need to make sure that no one eats too much and hurt themselves. It is okay if you don’t assign plates to some of your friends, but all plates should be assigned to someone. Same plate cannot be assigned to more than one of your friends.

Write a program to minimize the total number of peanuts eaten by the friend who eats the most number of peanuts.

Limits

Time Limit: 1s
Memory Limit: 256MB

Input Format

The first line of the input has 2 integers N and F respectively, separated by a space. The number of plates and the number of friends. Each of the following N lines have a single integer, A_i the number of peanuts in the i^th plate. There can be empty plates too. (0 peanuts in the plate)

Output Format

Output just one integer representing your answer, the total number of peanuts eaten by the friend who eats most peanuts.

Constraints

• 1 \(\leq\) N \(\leq\) 10⁶
• 1 \(\leq\) F \(\leq\) 10³
• 1 \(\leq\) A_i \(\leq\) 10³

Sample Input 0

6 3
4
2
3
7
1
9

Sample Output 0

9