Problem 1C. 连续最大和

Limits

时间限制：1000ms

内存限制：128MB

Background

2022年，南京师范大学迎来了 120周年校庆 ，为了迎接校庆的到来，学校准备购买一些气球欢迎来客。于是学校便派小王同学去购买气球，小王同学的钱有限，所以他希望买到的气球越多越好。店主知道小王的想法后，给他提供了一个方法......

Description

店里一共有 \(n\) 束气球，编号为 \(0\) ~ \(n-1\) ，每束气球上有若干个气球，店主告诉小王每一束气球价格都是一样的，小王只能购买编号 连续的 \(k\) 束气球。在选择连续的 \(k\) 束气球之前，小王可以进行最多 \(k\) 次的有条件的交换操作，交换条件是 编号为 \(i\) 和 \(j\) 能交换当且仅当 \(i \equiv j (mod k)\) (即 \(i\) 和 \(j\) 模 \(k\) 同余)。小王想知道最多能买到多少气球。

Input

第一行两个整数 \(n\) , \(k\) ，含义见描述；

第二行 \(n\) 个整数，第 \(i\) 个数代表编号为 \(i-1\) 的那束气球上的气球个数。

Output

输出一行，表示最多能买到的气球数量。

Samples

Sample Input 1

4 2
2 7 3 4

Sample Output 1

10

提示：购买编号为1和2的两束气球即为最大值。或者也可以把编号为1和3的两束气球交换，变成2 4 3 7，再购买最后两束气球，也可以得到最大值

Sample Input 2

3 3
99999999 99999999 99999999

Sample Output 2

299999997

Data range

对于50% 数据，\(1 \leq k \leq n \leq 100\)，对于 100% 数据，\(1 \leq k \leq n \leq 2 \times 10^5\)。

每束气球个数 \(x\) 满足 \(0 \leq x \leq 10^9\) 。

注意， 答案可能超出32位整数的范围 。