Largest Value

Interview

Time limit2sMemory limit512 MB

Summary

Choose M disjoint contiguous groups in an array of up to 20 numbers so the total sum of their elements is as large as possible.

Level: Medium7 of 10
Topics: Dynamic programming, Prefix sum, Binary search
Solved: No attempts yet

Problem

A sequence of N integers is given. A contiguous subsequence consisting of one or more numbers from the given sequence is called a "group". Given a positive integer M, write a program that selects M groups and finds the maximum possible sum of all numbers belonging to the groups.

Input

The first line gives N and M (1 ≤ M ≤ N ≤ 20). The second line gives the numbers in the sequence. The numbers are separated by spaces, and each is an integer whose absolute value is less than or equal to 100.

Output

On the first line, print the maximum sum of all numbers belonging to the groups when M groups are selected.

Examples2

Example 1
Input
```
10 2
10 -4 3 1 5 6 -35 12 21 -1
```
Expected output
```
54
```
Example 2
Input
```
10 3
10 -4 3 1 5 6 -35 12 21 -1
```
Expected output
```
58
```