配点 : 300 点
問題文
1 从 N 有 N 苹果。 苹果 i 的美味 A_i 。 A_i 也可能为负。 另外,整数 给出了 K 。
您可以多次执行以下操作( 它可以重复(甚至0 次)。
- 整数 i (1 \leq i \leq N-K+1)并选择苹果 吃 i,i+1,\cdots,i+K-1 。 请注意,对于之前操作中已经吃掉的苹果,不会执行任何操作。
最后,找出你吃的苹果的美味程度的最大可能总和。
制約
- 1 \leq K \leq N \leq 250000
- -10^9 \leq A_i \leq 10^9
- 所有输入值都是整数。
入力
输入是按以下格式从标准输入给出的。
N K A_1 A_2 \cdots A_N
出力
打印答案。
入力例 1
4 2 2 -1 2 -2
出力例 1
3
可以进行以下操作。 选择
- i=1 和苹果 吃 1,2 。 吃
- i=2 和苹果 吃 3 。 (苹果 2 已经被吃掉了,所以什么也不做)
此时吃到的苹果总的好吃度是 它变成 A_1+A_2+A_3=3 。 无论你如何操纵它,你吃的苹果的总美味将是 它不会超过 3 。 因此答案是 3 。
入力例 2
5 5 3 1 4 1 5
出力例 2
14
入力例 3
5 1 -1 -2 -3 -4 -5
出力例 3
0
入力例 4
20 4 573641910 -499039319 421342458 893335602 -961457884 -190195710 -497364364 -954575123 41286305 -310659388 -451608793 122064200 -719921087 87712135 43831420 714154567 -451280 -161259952 488561040 -501663741
出力例 4
2561828581