题目描述

给定一个长度为 $n$ 的整数序列 $a$，元素可以为负。

有一个长度为 $n$ 的 01 序列 $s$，初始所有元素都为 $0$。你可以进行下面两种操作任意次：

• 选择 $s$ 中 $k$ 个连续的 $0$，把它们变为 $1$。
• 选择 $s$ 中 $k$ 个连续的 $1$，把它们变为 $0$。

其中 $k$ 为给定常数。请最大化 $\sum_{i=1}^ns_ia_i$。

输入格式

输入数据第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数，表示序列 $a$。

输出格式

输出一行一个整数表示 $\sum_{i=1}^ns_ia_i$ 的最大可能值。

样例

Sample Input #1

6 3
5 -1 -4 1 -1 4

Sample Output #1

8

Sample #2 & Sample #3

见下发文件。

约束

• 对于前 $20\%$ 的数据，$n\leq 20$。
• 对于前 $50\%$ 的数据，$n\leq 100$。
• 对于另外 $10\%$ 的数据，$k=1$。
• 对于另外 $10\%$ 的数据，$k=2$。

对于 $100\%$ 的数据，$1 \leq k\leq n\leq 500$，$|a_i|\leq 10^9$。