You are given a dequeue with 4 operations

1: take out the element from left side of the dequeue

2: take out the element from right side

3: insert the element (which was previously taken out) from left side

4: insert the element (which was previously taken out ) from right side

The maximum number of operations that can be done is given by k.

Now with these operations we have to get the maximum sum of the elements taken out .

Input: first line consists N and K ,N being the size of the deque and K being the maximum operations that can be performed, the second line consists N elements of the dequeue .

Ex: 6 4

-6 -100 50 -2 -3 -5

output: 44

Explanation: Remove 3 elements from left side and insert -100 back to the dequeue , so the sum of remaining elements would be 44.

Ex: 6 3

-6 -100 50 -2 -3 -5

output: 0

Explanation: cannot get positive sum.