← 返回题目列表

AtCoder · iroha2019_day1_g

G. 大于朋友,小于恋人

中文机器翻译题面 查看原题

配点: 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