G - 友達以上恋人以下 /

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