You have just written an line essay for English. Each line is numbered from to , and line is given a *value* of .

A paragraph is defined as a *subarray* of lines from the essay. Note that a paragraph may contain of a single line. The *score* of a paragraph is maximum *value* of any line in the paragraph. The *total score* of the essay is the sum of the *scores* of all the paragraphs.

Your teacher wants the essay to have at most paragraphs, otherwise he is too lazy to read it and will give you a zero! Not wanting a zero, you plan to split the lines in your essay into at most paragraphs. However, you want to maximize the *total score* in order to have the best chance of receiving a good mark.

What is the maximum possible *total score* of the essay, if you split it into at most paragraphs?

#### Input Specification

The first line will contain two integers, , the number of lines in your essay, and the maximum number of paragraphs in your essay.

The next line will contain integers, , the score of each line.

#### Output Specification

Output a single integer, the maximum possible *total score*.

#### Subtasks

##### Subtask 1 [10%]

##### Subtask 2 [40%]

##### Subtask 3 [50%]

No further constraints.

#### Sample Input 1

```
5 3
1 4 2 3 5
```

#### Sample Output 1

`12`

#### Explanation For Sample 1

- The first paragraph can contain lines 1 and 2, for a score of .
- The second paragraph can contain lines 3 and 4, for a score of .
- The third paragraph can contain line 5, for a score of .

#### Sample Input 2

```
3 2
1 2 1
```

#### Sample Output 2

`3`

## Comments