Maximum Sum of At Most k Non-Overlapping Subarrays

Given an integer n and an integer k, and a sequence of n integers, find the maximum sum obtainable by choosing at most k non-overlapping subarrays. Each subarray must be contiguous and non-empty. Note that you are allowed to choose fewer than k subarrays, or even no subarray at all (in which case the sum is 0). Formally, if the sequence is a[1], a[2], ..., a[n], you need to partition a subset of these elements into at most k disjoint segments such that the sum of all elements in these segments is maximized.

If all numbers are negative, it might be optimal to choose none of them, yielding a result of 0.

The solution must be efficient given the sequence length.

inputFormat

The input begins with two integers n and k in one line, where n is the number of elements in the sequence and k is the maximum number of non-overlapping subarrays that can be chosen. The next line contains n integers separated by spaces.

Constraints (as implied by the problem):

• 1 ≤ n ≤ 10^5 (for example)
• 1 ≤ k ≤ n
• -10^9 ≤ a[i] ≤ 10^9

outputFormat

The output contains a single integer — the maximum sum achievable.

sample

5 2
1 2 -1 2 3

8