Members of CCLUB are planning to play Minecraft, but they hate mining. Therefore, they created a bot to calculate how much profit they would make from mining consecutive mining areas. This bot will calculate and show the number of profits or losses from sequential mining areas.

Members decided that each member needs to mine a sequential group of mining areas (mining site). Can you find the maximum profit they would make from mining?

Mining sites of members can not overlap.

Every member has to mine a mining site.

Selected mining sites of 2 cclub members can be adjacent to each other.

Input

The first line will contain 2 integers: How many mining areas there are, \(\mathbf{N}\) and participating CCLUB members \(\mathbf{K}\).

• \(\mathbf{K}\leq\mathbf{N}\leq 10^5\)
• \(1\leq\mathbf{K}\leq 10^3\)

The second line contains \(\mathbf{N}\) numbers, the profit or loss from that mining area.

• \(-100\leq\mathbf{a_i}\leq 100\)

Output

The maximum profit that can be made from mining.

Example

Input 1:

9 3
-3 1 5 -1 10 100 -5 -2 4

Output 1:

120

Input 2:

8 1
-2 1 3 -1 1 1 -5 4

Output 2:

5

Explanation

Input 1

• 1st member will mine [1,5] sequential mining sites whose index is between 1 and 2.
• 2nd member will mine [10,100] sequential mining sites whose index is between 4 and 5.
• 3rd member will mine [4] sequential mining sites whose index is between 8 and 8.

Input 2

• 1st member will mine [1,3,-1,1,1] sequential mining sites whose index is between 1 and 5.