/ 
Time Limit: 2 sec / Memory Limit: 512 MB
配点 : 700 点
問題文
高橋君の家にはパネルが一列に N 個並んでおり、1,2,...,N と順に番号がついています。パネル i には数 A_i が書いてあり、高橋君はこれらのパネルに球を当てて遊んでいます。
高橋君は球を K 回投げました。高橋君は i 回目に球を当てたパネルをパネル p_i としたとき、このゲームの得点を i \times A_{p_i} の和と定めました。
さて、高橋君は K 回球を投げ終わり得点を計算しようとしましたが、自分が当てたパネル p_1,p_2,...,p_K を忘れてしまいました。高橋君は唯一、 1 ≦ i ≦ K-1 を満たすすべての i に対して 1 ≦ p_{i+1}-p_i ≦ M が成り立っていたことを覚えています。この情報をもとに高橋君の得点として考えられる最大値を求めてください。
制約
- 1 ≦ M ≦ N ≦ 10^5
- 1 ≦ K ≦ min(300,N)
- 1 ≦ A_i ≦ 10^{9}
部分点
- 100 点分のデータセットでは、M = N が成り立つ。
- 200 点分のデータセットでは、N ≦ 300 , K ≦ 30 が成り立つ。
- 300 点分のデータセットでは、K ≦ 30 が成り立つ。
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 A_2 ... A_N
出力
高橋君の得点として考えられる最大値を出力せよ。
入力例1
5 2 3 10 2 8 10 2
出力例1
56
1,3,4 のパネルにこの順に当てたとき、最大となります。
入力例2
5 5 2 5 2 10 5 9
出力例2
28
この入力は M = N の部分点の制約を満たします。
入力例3
10 3 5 3 7 2 6 9 4 8 5 1 1000000000
出力例3
5000000078
Score : 700 points
Problem Statement
There are N panels arranged in a row in Takahashi's house, numbered 1 through N. The i-th panel has a number A_i written on it. Takahashi is playing by throwing balls at these panels.
Takahashi threw a ball K times. Let the panel hit by a boll in the i-th throw be panel p_i. He set the score for the i-th throw as i \times A_{p_i}.
He was about to calculate the total score for his throws, when he realized that he forgot the panels hit by balls, p_1,p_2,...,p_K. The only fact he remembers is that for every i (1 ≦ i ≦ K-1), 1 ≦ p_{i+1}-p_i ≦ M holds. Based on this fact, find the maximum possible total score for his throws.
Constraints
- 1 ≦ M ≦ N ≦ 100,000
- 1 ≦ K ≦ min(300,N)
- 1 ≦ A_i ≦ 10^{9}
Partial Scores
- In the test set worth 100 points, M = N.
- In the test set worth another 200 points, N ≦ 300 and K ≦ 30.
- In the test set worth another 300 points, K ≦ 30.
Input
The input is given from Standard Input in the following format:
N M K A_1 A_2 … A_N
Output
Print the maximum possible total score for Takahashi's throws.
Sample Input 1
5 2 3 10 2 8 10 2
Sample Output 1
56
The total score is maximized when panels 1,3 and 4 are hit, in this order.
Sample Input 2
5 5 2 5 2 10 5 9
Sample Output 2
28
This case satisfies the additional constraint M = N for a partial score.
Sample Input 3
10 3 5 3 7 2 6 9 4 8 5 1 1000000000
Sample Output 3
5000000078