Maximum Sum of Up to M Contiguous Segments

On her 18th birthday, ftiasch was shown a magical sequence \(A_1, A_2, \ldots, A_N\) by lqp18_31. She is allowed to choose at most \(M\) contiguous segments from the sequence as her birthday gift. Naturally, ftiasch wants to know the maximum possible sum of the elements from the chosen segments. Note that you may choose fewer than \(M\) segments (even none) if it leads to a better outcome. Help her determine the maximum sum.

Important: A contiguous segment is defined as a sequence of consecutive elements in \(A\). The segments chosen must not overlap.

inputFormat

The input consists of two lines:

• The first line contains two integers \(N\) and \(M\) separated by a space, where \(N\) represents the number of elements in the sequence, and \(M\) is the maximum number of contiguous segments you may choose.
• The second line contains \(N\) integers \(A_1, A_2, \ldots, A_N\) separated by spaces.

outputFormat

Output a single integer representing the maximum sum of the elements from the selected segments.

If all elements are negative, it is allowed to choose no segments, in which case the answer is 0.

sample

5 2
1 -2 3 4 -1

8