G - 友達以上恋人以下
Editorial
/
Time Limit: 1 sec / Memory Limit: 256 MB
配点: 400 点
この問題の解説はこちら。
問題文
※きたむーとはこの問題の作問のお手伝いをした人の名前である。また、きたむーの彼女はいろはちゃんではない。
これはきたむーが彼女を射止める前の話である。彼は彼女に事前に伝えられていた。
「あなたは友達以上恋人以下」
と。彼は思った。
「つまり恋人も含むよね??恋人になってもいいですよってことだよね??ね??」
というわけで彼は思いを伝えることにしたが、いきなり思いを伝えても受け入れてもらえないかもしれない。そこで、彼は何日かに分けて少しずつ思いを伝えることにした。
きたむーは明日から N 日間のうちちょうど M 日に彼女のもとへ行き、好意をほのめかす。なお、それぞれの日の彼女の機嫌は A_i であるとあらかじめ予想できているため、彼は極力機嫌のいい日に彼女のもとへ行きたい。しかし、あまり時間が空きすぎてはよくないと考えた彼は、 K 日以上時間を空けない、つまり連続する K 日に1回は好意をほのめかすことにした。ただし、今日は既に好意をほのめかしている。
あなたはきたむーの行動をシミュレートしたくなった。きたむーが好意をほのめかす日の彼女の機嫌の合計の最大値を求めよ。
制約
- 入力される値はすべて整数である
- 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
出力
きたむーが好意をほのめかす日の彼女の機嫌の合計の最大値を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