## 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``` PetarV: 2012-04-21 13:19:01 You probably didn't get WA 49. There are 50 tests and I think it is SPOJ's procedure to go through all the testdata, then return WA with the timestamp of the first testcase that failed. Given that your execution times are around 0.01s, I'd say that you got WA on one of the first test cases. Ivaylo Chernev: 2012-04-19 10:36:16 How many test are there ?? I got WA 49 :O