Maximum Total Interest in Circular Study Schedule

gyx wants to study OI with all his available time over a year of n days. Every day has an interest value for studying OI; however, due to life issues, some days the interest value may be negative. gyx has k types of OI knowledge to master and insists that each type must be learned in one uninterrupted block of consecutive days (at least one day per topic). In between these OI study blocks, he may study cultural courses. Also, the order in which he studies the k topics is arbitrary.

You are allowed to choose a starting day (an integer from 1 to n). Then, the study plan will cover n consecutive days in a circular fashion (i.e. if the days run out, they wrap around to the beginning). Under the constraint that in the chosen n days all k topics must be learned (i.e. you must select exactly k non-overlapping continuous segments from the chosen days), your task is to determine the maximum total sum of interest values over the days that are allocated to studying OI.

Note: Each OI learning segment must contain at least one day and the segments cannot overlap, though there may be gaps (days used for cultural courses) between them.

The problem can be modeled as follows: Given a circular array of n integers (which represent the interest values), choose exactly k disjoint contiguous subarrays (each of at least length 1) so that the total sum is maximized. You are free to choose the starting point of the circular array.

The answer must be output as a single integer representing the maximum total interest sum.

inputFormat

The first line contains two integers n and k (1 ≤ k ≤ n), where n is the number of days in a year and k is the number of OI topics to be learned.

The second line contains n integers, representing the interest values for OI on each day. The days are arranged in order and the schedule is circular.

outputFormat

Output a single integer — the maximum total interest sum obtainable for the days selected for studying OI.

sample

5 2
1 2 -1 2 3

8