## SFLIP - Segment Flip

no tags

You are given N number a1, a2, ... , aN. In a segment flip, you can pick a contiguous segment ai, ai+1, ... , aj of these numbers, where i<=j and negate all the numbers in this segment.

You are permitted atmost K segment flip operations overall. Also, no 2 segments that you pick can overlap. That is, if you flip ai, ... , aj and ak, ... , al then either j < k or l < i.

Your aim is to maximize the sum of all the numbers in the resulting sequence by applying appropriate segment flip operations meeting these constraints.

For instance, suppose the sequence is -5, 2, -3 and you are allowed a single segment flip. The best sum you can achieve is 6, by flipping all 3 numbers as a single segment to 5, -2, 3.

### Input

The first line contains 2 integers N and K. The next line contains N integers, the initial values of a1, a2, ... , aN.

### Output

A single integer denoting the maximum possible sum of the final array.

### Constraints

0 <= K <= N
-10000 <= ai <= 10000
1 <= N <= 100000

### Example

```Input:
3 1
-5 2 -3

Output:
6```