M. Merging Slimes
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In a certain RPG, there are $$$n$$$ slimes lined up in a row, numbered from $$$1$$$ to $$$n$$$ from left to right. Each slime can be of water-type, fire-type, or elementless. The power of the $$$i$$$-th slime is represented by a signed integer $$$a_i$$$. Specifically:

  • If $$$a_i \gt 0$$$, the slime is of water-type, and its power is $$$a_i$$$.
  • If $$$a_i \lt 0$$$, the slime is of fire-type, and its power is $$$\vert{}a_i\vert{}$$$ (which is equal to $$$-a_i$$$).
  • If $$$a_i = 0$$$, the slime is elementless, and its power is $$$0$$$ (representing no energy or power value).

As a player, you will use a water-type magic to attack these slimes. The mana cost to attack a single slime is determined as follows:

  • If its represented power $$$a_i \gt 0$$$, the mana cost is $$$a_i$$$.
  • If its represented power $$$a_i \le 0$$$ (meaning the slime is fire-type or elementless), the mana cost is $$$0$$$.

To minimize the total mana cost, you can perform at most $$$k$$$ merging operations before casting the magic:

  • Select two adjacent slimes with represented powers $$$a$$$ and $$$b$$$, and merge them into a single slime. The represented power of the newly merged slime will be $$$a+b$$$.
Note that if two slimes of opposite types and equal power are merged, they will neutralize each other, resulting in an elementless slime with a power of $$$0$$$.

After performing at most $$$k$$$ operations, you cast the magic. The total final cost will be the sum of the mana costs required to attack all remaining slimes.

Find the minimum possible total cost if you use an optimal strategy.

Input

The first line contains two integers $$$n$$$ and $$$k$$$, representing the number of slimes and the maximum number of merging operations you can perform.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, representing the initial represented powers of the slimes.

  • $$$1 \le n \le 3000$$$
  • $$$0 \le k \lt n$$$
  • $$$-10^9 \le a_i \le 10^9$$$
Output

Output a single integer, representing the minimum possible total cost.

Examples
Input
3 1
10 -10 5
Output
5
Input
5 2
3 -5 4 -2 6
Output
7
Input
4 2
5 -5 8 -8
Output
0