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

题目描述

璃月港的千岩军后勤部门发起了「战备物资积分申领」活动 , 为驻守绝云间与荻花洲的将士筹备物资

旅行者受胡桃所托参与活动 , 需在规定期限内合理申领积分

活动规则如下：

• 活动持续 $\rm N$ 天 , 第 $\rm i$ 天前往千岩军后勤点申领 , 可获得 $\rm A_i$ 点战备积分

• 千岩军执行严格的「周期核查」制度：以任意连续 $\rm K$ 天为一个核查周期 , 若单个参与者在某周期内申领次数超过 $2$ 次 , 将被判定为「违规申领」——依据璃月契约精神 , 所有已获得的积分将被清零

• 每日仅能申领一次 , 不可重复领取

请帮旅行者规划申领日程 , 计算能获得的最大战备积分总和

输入格式

第一行输入两个空格分隔的整数 $\rm N,K$

第二行输入 $\rm N$ 个整数表示 $\rm A_i$ , 即第 $\rm i$ 天可申领的战备积分

输出格式

输出一个整数 , 表示旅行者在遵守规则的前提下 , 能获得的最大战备积分总和

5 4
1 3 2 4 3

8

样例1解释

合理的申领方案为第 $1$、$4$、$5$ 天前往后勤点：

核查周期覆盖情况：$1 \sim 4$ 天申领 $1$ 次 , $2 \sim 5$ 天申领 $2$ 次 , 均未违规

总积分 $1+4+3=8$

5 2
3 3 2 2 1

11

样例2解释

核查周期为 $2$ 天 , 任意连续 $2$ 天内申领次数均不超过 $2$ 次 , 因此可每天申领：

总积分 $3+3+2+2+1=11$

12 5
982414169 751638377 96719183 8014826 2138351 9172397 640431916 9819995 3478604 18254225 2082841 93502728

2486241415

样例4

点此下载

数据规模

测试点 $1 \sim 3$ 满足 $\rm 1 \leq N \leq 20$

测试点 $4 \sim 8$ 满足 $\rm 1 \leq N \leq 3000 , 1 \leq K \leq 10$

测试点 $9 \sim 16$ 满足 $\rm 1 \leq K \leq N \leq 300$

测试点 $19 \sim 25$ 满足 $\rm 1 \leq K \leq N \leq 3000,1 \leq A_i \leq 10^9$