配点: 400 点
这个问题的解释是单击此处。
問題文
*Kitamu 是帮助撰写此问题的人的名字。而且,Kitamu的女朋友不是伊吕波。
这是在 Kitamu 抓住她之前。他已经提前告诉她了。
“你们不仅仅是朋友,还不是恋人。”
和。他想。
“这也包括恋人吧?也就是说,做恋人也没关系吧??”
所以他决定表达自己的感受,但即使他突然表达了自己的感受,也不一定会被接受。于是,他决定用几天的时间,一点点地传达自己的想法。
Kitamu 明天开始 N 几天之内 M 去找她并暗示你喜欢她。而且,她每天的心情都是 既然他能预见 A_i 也会一样,他想在心情好的时候去找她。不过,他觉得空闲时间太多也不好。 K 间隔不超过一天,即连续 K 天1我决定暗示偏袒。不过,今天他已经暗示了偏袒。
您想要模拟 Kitamu 的动作。求 Kitamu 暗示喜欢她那天的情绪总和的最大值。
制約
- 所有输入值均为整数
- 1 \leq N \leq 365
- 1 \leq M \leq N
- 1 \leq K \leq N
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
入力
输入是按以下格式从标准输入给出的。
N M K A_1 A_2 \cdots A_N
出力
计算 Kitamu 暗示她喜欢的那一天她的情绪的最大总和。
输出为1行。但是,如果没有满足条件的选择方法,-1。
入力例 1
5 2 3 5 1 3 2 4
出力例 1
8
例如,1日和3如果你当天暗示你的好感,总的心情会是8变为。总的心情是9绝不会仅限于此。
入力例 2
2 1 1 100 100
出力例 2
-1
入力例 3
1 1 1 100
出力例 3
100
入力例 4
10 6 4 56 1 82 32 4 11 74 49 90 6
出力例 4
383