这里还有一个关于数组的问题。给定正整数 len 和数组 a,其中包含 n 个整数 a1, a2, ..., an。让我们介绍给定数组的两个特征。
- 让我们考虑长度为 len 的数组的任意区间,从位置 i 开始。值 $$\text{modSum}(i, \text{len}) = \left| \sum_{j=i}^{i+\text{len}-1} a_j \right|$$ 是所选区间上的模和。换句话说,模和是所选区间上长度为 len 的整数之和,取其绝对值。
- 值 $$\max_{1 \leq i \leq n - len + 1} modSum(i, len)$$ 是数组的最佳总和。换句话说,数组的最优和是长度为 len 的数组的各个区间上的所有模和的最大值。
你的任务是计算给定数组 a 的最佳和。然而,在进行计算之前,您只能使用该数组产生不超过 k 个以下形式的连续运算:一次运算意味着从数组 ai 中取出任意数字并将其乘以 -1。换句话说,最多允许您从数组中取出任意数字 ai 并用 -ai 替换它。数组中的每个数字都可以选择任意次数。
你的任务是在完成上述最多 k 个操作后计算数组的最大可能最优和。
输入
第一行包含两个整数 n, len (1 ≤ len ≤ n ≤ 105) — 数组中元素的数量以及数组中所选子区间的长度。
第二行包含一个由 n 个整数 a1, a2, ..., an (|ai| ≤ 109) 组成的序列 — 原始数组。
第三行包含一个整数 k (0 ≤ k ≤ n) — 允许的最大操作数。
行中的所有数字均由一个空格分隔。
输出
在完成不超过 k 个可接受的操作后,在单行中打印最大可能的最佳总和。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
5 3 0 -2 3 -5 1 2
输出 #1
10
输入 #2
5 2 1 -3 -10 4 1 3
输出 #2
14
输入 #3
3 3 -2 -5 4 1
输出 #3
11