And here goes another problem on arrays. You are given positive integer len and array a which consists of n integers a₁, a₂, ..., a_n. Let's introduce two characteristics for the given array.

• Let's consider an arbitrary interval of the array with length len, starting in position i. Value , is the modular sum on the chosen interval. In other words, the modular sum is the sum of integers on the chosen interval with length len, taken in its absolute value.
• Value is the optimal sum of the array. In other words, the optimal sum of an array is the maximum of all modular sums on various intervals of array with length len.

Your task is to calculate the optimal sum of the given array a. However, before you do the calculations, you are allowed to produce no more than k consecutive operations of the following form with this array: one operation means taking an arbitrary number from array a_i and multiply it by -1. In other words, no more than k times you are allowed to take an arbitrary number a_i from the array and replace it with -a_i. Each number of the array is allowed to choose an arbitrary number of times.

Your task is to calculate the maximum possible optimal sum of the array after at most k operations described above are completed.