You are given N number a₁, a₂ ... a_N. In a segment flip, you can pick a contiguous segment a_i, a_i+1 ... a_j 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 a_i ... a_j and a_k ... a_l 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 a₁, a₂ ... a_N.

Output

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

Constraints

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

Example

Input:
3 1
-5 2 -3

Output:
6