某城市计划在一条主要街道两侧建设电动汽车充电桩，以满足日益增长的充电需求。街道被划分为 n 个连续的区域，每个区域都有预估的充电需求量。 为了最大化投资效益，规划部门希望选择 m 个区域建设大型充电站（每个充电站占据一个区域），并且要求任意两个充电站之间的距离至少为 k 个区域。 给定街道各区域的充电需求预测数据，请帮助规划部门确定最优的充电站布局方案，使得所选区域的充电需求总和最大。 注意：距离是指两个区域索引之间的差值，例如区域 i 和区域 j 之间的距离为 abs(i−j) 。
输入描述
三个整数 n、m、k，分别表示区域总数、计划建设的充电站数量、充电站间的最小距离要求 整数数组 Q ，表示各区域的充电需求量 1. 区域数量 n ：1≤n≤2000 2. 充电站数量 m ：1≤m≤200 3. 最小距离 k ：1≤k≤100 4. 各区域充电需求：0 ≤ 需求 ≤ 10000
输出描述
返回一个整数，表示在满足约束条件下能够获得的最大充电需求总和。 注意：测试用例 Q 保证输入数据合法，至少存在一种满足条件的选址方案
示例
示例 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
时间限制 1000 ms · 内存限制 128 MB