题目描述

又是一道关于数组的题目。给定正整数 $len$ 和一个由 $n$ 个整数 $a_1, a_2, \ldots, a_n$ 组成的数组 $a$。先为该数组引入两个特征值：

• 考虑数组中一个从位置 $i$ 开始、长度为 $len$ 的任意区间。值 $modSum(i, len) = \left| \sum_{j=i}^{i+len-1} a_j \right|$ 称为该区间的模和。换句话说，模和就是所选取的长度为 $len$ 的区间上所有整数的和的绝对值。
• 值 $\max_{1 \le i \le n-len+1} \; modSum(i, len)$ 称为数组的最优和。换句话说，数组的最优和就是所有长度为 $len$ 的区间的模和的最大值。

你的任务是计算给定数组 $a$ 的最优和。不过在计算之前，你最多可以执行 不超过 $k$ 次如下操作：每次操作任取数组中的一个数 $a_i$ 并把它乘以 -1。换句话说，最多 $k$ 次，你可以任取数组中的一个数 $a_i$ 并把它替换为 $-a_i$。数组中的每个数都可以被选取任意多次。

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

输入格式

第一行包含两个整数 $n$、$len$（$1 \le len \le n \le 10^5$），分别表示数组元素个数和所选子区间的长度。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$|a_i| \le 10^9$），即原始数组。第三行包含一个整数 $k$（$0 \le k \le n$），即允许的最大操作次数。行内数字均用单个空格隔开。

输出格式

一行输出执行不超过 $k$ 次操作后可能的最大最优和。

5 3
0 -2 3 -5 1
2

10

5 2
1 -3 -10 4 1
3

14

3 3
-2 -5 4
1

11