D - Part-Time Job Planning Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、1 日目から N 日目までの N 日間の計画を立てています。

i 日目（1 \le i \le N）にアルバイトをすると、A_i 円の給料を得ることができます。

高橋君は体調を崩さないよう、以下の条件を満たすようにアルバイトをする日を選ばなければなりません。

  • アルバイトをする日数は合計で K 日以下である。
  • i 日目にアルバイトをした場合、その後 D 日間、すなわち i + 1 日目から i + D 日目までの間はアルバイトをすることができない。

高橋君が適切にアルバイトをする日を選んだとき、得られる給料の合計の最大値を求めてください。

制約

  • 1 \le N \le 5000
  • 1 \le K \le N
  • 0 \le D \le N
  • 1 \le A_i \le 10^9（1 \le i \le N）
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K D
A_1 A_2 \dots A_N
  • 1 行目には、計画の日数を表す N、アルバイトができる最大日数を表す K、必要な休養日数を表す D が、スペース区切りで与えられる。
  • 2 行目には、各日にアルバイトをした場合に得られる給料を表す N 個の整数 A_1, A_2, \dots, A_N が、スペース区切りで与えられる。

出力

高橋君が得られる給料の合計の最大値を 1 行に出力せよ。

入力例 1

5 3 1
2 5 3 4 1

出力例 1

9

入力例 2

6 3 0
3 8 1 5 9 2

出力例 2

22

入力例 3

15 5 2
12 45 80 15 90 23 100 5 30 75 10 60 85 40 50

出力例 3

340

入力例 4

25 8 2
834729103 129482710 948172635 348172938 748192837 192837465 657483920 817263549 238475619 908172635 472819384 563728192 109283746 874635291 928374651 348271938 726154839 837462519 192837465 564738291 983746152 237485960 748392019 463728190 857392018

出力例 4

6570889021

入力例 5

1 1 1
1000000000

出力例 5

1000000000

Score : 366 pts

Problem Statement

Takahashi is making a plan for N days, from Day 1 to Day N.

If he works a part-time job on Day i (1 \le i \le N), he will earn a wage of A_i yen.

To avoid falling ill, Takahashi must choose the days to work so that the following conditions are satisfied:

  • He works for at most K days in total.
  • If he works on Day i, he cannot work for the following D days, that is, from Day i + 1 to Day i + D.

Find the maximum total wage Takahashi can earn by choosing the work days appropriately.

Constraints

  • 1 \le N \le 5000
  • 1 \le K \le N
  • 0 \le D \le N
  • 1 \le A_i \le 10^9 (1 \le i \le N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K D
A_1 A_2 \dots A_N
  • The first line contains N, representing the number of days in the plan, K, representing the maximum number of days he can work, and D, representing the number of rest days required, separated by spaces.
  • The second line contains N integers A_1, A_2, \dots, A_N separated by spaces, representing the wages earned if he works on each day.

Output

Print the maximum total wage Takahashi can earn in a single line.

Sample Input 1

5 3 1
2 5 3 4 1

Sample Output 1

9

Sample Input 2

6 3 0
3 8 1 5 9 2

Sample Output 2

22

Sample Input 3

15 5 2
12 45 80 15 90 23 100 5 30 75 10 60 85 40 50

Sample Output 3

340

Sample Input 4

25 8 2
834729103 129482710 948172635 348172938 748192837 192837465 657483920 817263549 238475619 908172635 472819384 563728192 109283746 874635291 928374651 348271938 726154839 837462519 192837465 564738291 983746152 237485960 748392019 463728190 857392018

Sample Output 4

6570889021

Sample Input 5

1 1 1
1000000000

Sample Output 5

1000000000