You have just written an ~N~ line essay for English. Each line is numbered from ~1~ to ~N~, and line ~i~ is given a value of ~v_i~.

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 ~K~ paragraphs, otherwise he is too lazy to read it and will give you a zero! Not wanting a zero, you plan to split the ~N~ lines in your essay into at most ~K~ 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 ~K~ paragraphs?

Input Specification

The first line will contain two integers, ~N, K~ ~(1 \le K \le N \le 10^5)~, the number of lines in your essay, and the maximum number of paragraphs in your essay.

The next line will contain ~N~ integers, ~v_i~ ~(1 \le v_i \le 10^9)~, the score of each line.

Output Specification

Output a single integer, the maximum possible total score.

Subtasks

Subtask 1 [10%]

~N \le 20~

Subtask 2 [40%]

~N \le 5000~

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 ~4~.
• The second paragraph can contain lines 3 and 4, for a score of ~3~.
• The third paragraph can contain line 5, for a score of ~5~.

~5 + 3 + 4 = 12~

Sample Input 2

3 2
1 2 1

Sample Output 2

3