题目描述

有 $N$ 个格子横向排列成一行。从左起第 $i$ 个格子上写有整数 $a_i$。

一开始，所有格子都是白色的。你可以任意次数重复以下操作：

• 选择连续的 $K$ 个格子，将它们全部涂成白色或全部涂成黑色。在此过程中，每个格子的颜色会被覆盖。

操作结束后，所有黑色格子上所写整数的总和即为得分。请你求出可能得到的最大得分。

输入格式

输入以如下格式从标准输入读入：

$N$ $K$ $a_1$ $a_2$ $...$ $a_N$

输出格式

输出可能得到的最大得分。

样例 1

输入

5 3
-10 10 -10 10 -10

输出

10

样例 2

输入

4 2
10 -10 -10 10

输出

20

样例 3

输入

1 1
-10

输出

0

样例 4

输入

10 5
5 -4 -5 -8 -4 7 2 -4 0 7

输出

17

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq K \leq N$
• $a_i$ 是整数。
• $|a_i| \leq 10^9$

样例解释 1

将从左起第 $2$、$3$、$4$ 个格子涂成黑色即可。

样例解释 2

例如，可以按如下方式操作：

• 将从左起第 $1$、$2$ 个格子涂成黑色。
• 将从左起第 $3$、$4$ 个格子涂成黑色。
• 将从左起第 $2$、$3$ 个格子涂成白色。

由 ChatGPT 4.1 翻译