配点 : 400 点
問題文
N 化学品水平排列。每种药物都有 整数值 効用 是固定的,从左边开始 i 药物目前的功效是 b_i 。这些值不一定是正值。
Kenkoooo 可以使用特殊的水平设备根据需要多次执行以下操作(尽管他不必这样做)。
- 连续排队 选择 K 药物。所选药物的所有作用 0 变为。
请注意,移动化学品是危险的,不能这样做。
之后,Kenkoooo 喝掉所有 N 药物。在此之前,N 我想尽可能地最大化每种药物的效果总和。运算后求该和的最大值。
制約
- 1 ≤ K ≤ N ≤ 2 × 10^5
- -10^9 ≤ b_i ≤ 10^9
- 所有输入值都是整数。
入力
输入是按以下格式从标准输入给出的。
N K b_1 : b_N
出力
操作后 输出 N 药物效果总和的最大值。
入力例 1
9 3 -1 -2 -3 4 5 -6 -7 -8 -9
出力例 1
9
以下是最佳过程的示例。
- 1 第一个操作:从左开始 选择第 1, 2, 3 药物。
- 2 第一个操作:从左开始 选择第 6, 7, 8 药物。
- 3 第一个操作:从左开始 选择第 7, 8, 9 药物。
此时,9 每种药物的效果总和为 0 + 0 + 0 + 4 + 5 + 0 + 0 + 0 + 0 = 9 。 对于
入力例 2
5 4 -1 -1 5 -1 -1
出力例 2
1
你应该把药全部喝掉,什么也不做。
入力例 3
9 5 30 -20 40 60 -90 50 -40 10 70
出力例 3
120
入力例 4
10 1 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000
出力例 4
5000000000