P2990 [USACO10OPEN] Cow Hopscotch G

题目描述

坐标轴上有 $N$ 个点，编号为$1...N$，每个点都有一个值 $V_i$。

从 $0$ 出发往 $N$ 方向跳，每次最多跳 $K$ 步，再从任意一点往 $0$ 的方向跳，并最终跳到 $0$ 。

跳回来时踩的点必须是跳过去时经过过的点的前一个。

求这样跳过去跳回原点能获得的最大价值。

输入格式

第一行两个整数 $N \ K \ (1 \le K \le N \le 250,000)$。

下来 N 个整数 $V_i( |V_i| \le 2 \times 10^9)$。

输出格式

一行一个整数，即获得的最大值。

输入输出样例 #1

输入 #1

6 3 
0 1 2 -3 4 5

输出 #1

12