CF182C.Optimal Sum

And here goes another problem on arrays. You are given positive integer len and array a which consists of n integers _a_1, _a_2, ..., 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.

这里又有一道关于数组的题目。给你一个正整数 $len$ 和一个由 $n$ 个整数 $a_1, a_2, \dots, a_n$ 组成的数组 $a$。我们为该数组定义两个特征：

• 考虑数组中任意一个长度为 $len$ 的区间，其起始位置为 $i$。值
  
  称为该区间的模和（modular sum）。换言之，模和即该长度为 $len$ 的区间内所有整数之和的绝对值。

• 值
  
  称为该数组的最优和（optimal sum）。换言之，数组的最优和即所有长度为 $len$ 的区间所对应的模和中的最大值。

你的任务是计算给定数组 $a$ 的最优和。但在进行计算之前，你最多可以对该数组执行 $k$ 次连续操作（即操作次数不超过 $k$），每次操作的形式如下：任选数组中的一个数 $a_i$，将其乘以 $-1$。换句话说，你最多可以执行 $k$ 次操作，每次任选数组中一个数 $a_i$，并将其替换为 $-a_i$。数组中的每个数可被选中任意多次。

你的任务是：在至多执行上述 $k$ 次操作后，求出数组最优和所能达到的最大可能值。

The first line contains two integers n, len (1 ≤ len ≤ n ≤ 105) — the number of elements in the array and the length of the chosen subinterval of the array, correspondingly.

The second line contains a sequence consisting of n integers _a_1, _a_2, ..., a__n (|a__i| ≤ 109) — the original array.

The third line contains a single integer k (0 ≤ k ≤ n) — the maximum allowed number of operations.

All numbers in lines are separated by a single space.

第一行包含两个整数 $n$、$\text{len}$（$1 \leq \text{len} \leq n \leq 10^5$）—— 分别表示数组中元素的个数以及所选子区间的长度。

第二行包含一个由 $n$ 个整数 $a_1, a_2, \dots, a_n$（$|a_i| \leq 10^9$）组成的序列 —— 即原始数组。

第三行包含一个整数 $k$（$0 \leq k \leq n$）—— 表示允许执行操作的最大次数。

每行中的所有数字均以单个空格分隔。

In a single line print the maximum possible optimal sum after no more than k acceptable operations are fulfilled.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

在一行中输出执行不超过 $k$ 次可接受操作后所能达到的最大可能最优和。

请注意：在 C++ 中，请勿使用 %lld 说明符读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。