题目描述

奶牛们正在回味童年，玩一个类似跳格子的游戏，在这个游戏里，奶牛们在草地上画了一行 $N$ 个格子，编号为 $1\dots N$。

就像任何一个好游戏一样，这样的跳格子游戏也有奖励！第 $i$ 个格子标有一个数字 $v_i$ 表示这个格子的钱。奶牛们想看看最后谁能得到最多的钱。

规则很简单：

• 每个奶牛从 $0$ 号格子出发。($0$ 号格子在 $1$ 号之前，那里没钱)

• 然后她执行一个可能为空的跳跃序列前往格子 $N$。她每次落地所在的格子距离前一个格子最多 $K$ 个格子（例如，如果 $K=2$，从格子 $1$ 出发，她最多可以跳到格子 $2$ 或 $3$）。

• 在任何时候，她都可以选择回头往 $0$ 号格子跳，直到跳到 $0$ 号格子。

另外，除了以上规则之外（包括 $K$ 限制），回头跳的时候还有两条规则：

• 不可以跳到前进序列中的格子（格子 $0$ 除外）。

• 除了 $0$ 号格子之外，她在回来的时候，停留的格子必须是恰巧过去的时候停留的某个格子的前一格（尽管她可能在返回时做一些更大的跳跃，从而跳过一些潜在的返回格子）。

她赚取的金钱数量等于她跳过的所有格子的金钱价值之和。请找出奶牛能赚到的最大金额。

举例说明，考虑一个有六个格子的路线，其中 $K = 3$。

格子编号:       0      1      2      3      4      5      6 
            +---+  +---+  +---+  +---+  +---+  +---+  +---+ 
            |///|--|   |--|   |--|   |--|   |--|   |--|   | 
            +---+  +---+  +---+  +---+  +---+  +---+  +---+ 
值:            -      0      1      2     -3      4      5 

Bessie 的一种最优途径为（括号中表示当前格子的金钱收益）： $0[0] \to 1[0]\to 3[2]\to 6[5] \to 5[4] \to 2[1] \to 0[0]$。

如果 Bessie 跳了一个以 $0, 1, 2, 3, 4, \dots$ 开始的序列，那么她将无法返回，因为她无法合法地跳回到一个未被触碰过的格子上。

输入格式

第一行，两个用空格隔开的整数 $N, K$。

接下来 $N$ 行，每行一个整数 $V_i$。

输出格式

第一行，输出一个整数表示最大的钱数是多少。

6 3 
0 
1 
2 
-3 
4 
5 

12 

提示

【数据范围】

数据保证：$-2 \times 10 ^9 \le V_i \le 2 \times 10 ^ 9$，$3 \le N \le 2.5 \times 10^5$，$2 \le K \le N$。