题目内容

某城市计划在一条主要街道两侧建设电动汽车充电桩，以满足日益增长的充电需求。街道被划分为 $n$ 个连续的区域，每个区域都有预估的充电需求量。

为了最大化投资效益，规划部门希望选择 $m$ 个区域建设大型充电站（每个充电站占据一个区域），并且要求任意两个充电站之间的距离至少为 $k$ 个区域。

给定街道各区域的充电需求预测数据，请帮助规划部门确定最优的充电站布局方案，使得所选区域的充电需求总和最大。

注意：距离是指两个区域索引之间的差值，例如区域 $i$ 和区域 $j$ 之间的距离为 $abs(i-j)$。

输入描述

三个整数 $n$、$m$、$k$，分别表示区域总数、计划建设的充电站数量、充电站间的最小距离要求

整数数组，表示各区域的充电需求量

区域数量 $n$：$1 ≤ n ≤ 2000$

充电站数量 $m$：$1 ≤ m ≤ 200$

最小距离 $k$：$1 ≤ k ≤ 100$

各区域充电需求：$0 ≤$ 需求 $≤ 10000$

输出描述

返回一个整数，表示在满足约束条件下能够获得的最大充电需求总和。

注意：测试用例保证输入数据合法，至少存在一种满足条件的选址方案

样例1

输入

5,2,3,[10,20,30,40,50]

输出

70

说明

区域数量：$5$，计划建设 $2$ 个充电站，最小间距 $3$

各区域需求：$[10, 20, 30, 40, 50]$

最优选择：选择区域 $2$($20$) 和区域 $5$($50$)，它们之间距离为 $3$，满足最小距离要求

最大总需求：$20 + 50 = 70$

样例2

输入

5,2,2,[5,10,5,10,5]

输出

20

说明

区域数量：$5$，计划建设 $2$ 个充电站，最小间距 $2$ 各区域需求 $[5, 10, 5, 10, 5]$

最优选择：选择区域 $2$($10$) 和区域 $4$($10$)，它们之间距离为 $2$，满足最小距离要求

最大总需求：$10 + 10 = 20$

样例 3

输入

1,1,1,[10]

输出

10

说明

区域数量：$1$，计划建设 $1$ 个充电站，最小间距 $1$

各区域需求 $[10]$

最优选择：选择区域 $1$($10$)，只有 $1$ 个，满足最小距离要求

最大总需求：$10$