SFLIP - Segment Flip

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 at most 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

Added by:jack(chakradarraju)
Date:2011-08-10
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Proposed by venkateshb

hide comments
2012-04-21 13:19:01 PetarV
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.
2012-04-19 10:36:16 Ivaylo Chernev
How many test are there ?? I got WA 49 :O
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.