该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

文件读写

• 输入文件seat.in
• 输出文件seat.out

限制

• 1000ms
• 512MB

题目描述

元旦联欢会上，程老师在教室里摆了一排 $n$ 个座位，第 $i$ 个座位上放了一份价值 $a_i$ 的奖品。同学们可以入场挑选座位领奖，但程老师有一条维持秩序的规矩：

任意两个被挑选的座位之间，至少要隔 $d$ 个座位（即两个被选座位的编号之差必须大于 $d$）。

程老师想知道，在这条规矩下，同学们最多能领到总价值多少的奖品？

输入格式

第一行两个整数 $n, d$，分别表示座位数量和间隔要求。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个座位上奖品的价值。

输出格式

一行一个整数，表示最大奖品价值总和。

数据范围

特殊性质 A：$d = 1$（退化为"相邻不能同时选"的经典情形）。

特殊性质 B：所有奖品价值相同（即 $a_1 = a_2 = \cdots = a_n$）。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq d \leq n$，$1 \leq a_i \leq 10^4$。

5 1
2 7 3 5 4

12

5 2
2 7 3 5 4

11

4 3
1 2 3 4

4

样例解释

样例1：$d=1$，选 $2$ 号（价值 $7$）和 $4$ 号（价值 $5$），编号差 $2 > 1$，满足规矩，总价值 $7+5=12$。

样例2：$d=2$，选 $2$ 号（价值 $7$）和 $5$ 号（价值 $4$），编号差 $3 > 2$，满足规矩，总价值 $7+4=11$。