# 9367. Segment Flip

## Problem code: SFLIP

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.

Your aim is to maximize the sum of all the numbers in the sequence by applying appro-
priate segment

ips 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 three 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: 1s Source limit: 50000B Memory limit: 256MB Cluster: Pyramid (Intel Pentium III 733 MHz) Languages: All Resource: Proposed by venkateshb