Feast

Time limit1sMemory limit512 MB

Summary

Choose at most K disjoint non-empty subarrays of A so that the total sum of their elements is as large as possible.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Heap, Prefix sum
Solved: No attempts yet

Problem

Gug is preparing a feast for his friends. The feast consists of N plates of food arranged in a single row, and the ith plate from the left gives Ai points of satisfaction when eaten. Some plates of food might be rotten, so Ai can be negative.

A total of K people take part in the feast, and each person is assigned one consecutive segment of plates to eat. This segment can be empty. The segments of two people cannot overlap, because food cannot be eaten twice. Gug wants to assign the plates to his friends so that the sum of satisfaction points over all plates of food eaten is maximised.

Input

Your program reads from standard input.

The input starts with a line with two integers N and K.

The next line contains N integers A1, ..., AN.

Output

Your program writes to standard output.

The output should contain a single integer on a single line, the sum of satisfaction points in an optimal assignment.

Constraints

1 ≤ K ≤ N ≤ 3 × 105
0 ≤ |Ai| ≤ 109

Examples3

Example 1
Input
```
6 1
1 -2 3 -1 5 -6
```
Expected output
```
7
```
Example 2
Input
```
6 2
1 2 3 -10 5 6
```
Expected output
```
17
```
Example 3
Input
```
6 4
-1 -2 -1 0 -5 -1
```
Expected output
```
0
```