D - Advertisement Placement in the Exhibition Hall Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、展示会場の長い廊下に広告パネルを配置する仕事を任されました。廊下は 1 メートルごとにスロットが区切られており、全長 L メートルです。つまり、スロット 1, 2, \ldots, L が一列に並んでいます。

高橋君は N 枚の広告パネルを候補として持っています。N 枚の広告パネルはすべて区別されており、それぞれ設置するかしないかを独立に選べます。各パネルは最大 1 回まで設置でき、設置する場合は廊下上の好きな位置に（後述の制約を満たす限り）自由に配置できます。パネルを配置する順序や番号順による制約はありません。

i 番目の広告パネル（1 \leq i \leq N）は連続する w_i 個のスロットを占有します。具体的には、i 番目の広告パネルの左端をスロット s に合わせて設置すると、スロット s, s+1, \ldots, s+w_i-1 を占有します（ただし 1 \leq s かつ s + w_i - 1 \leq L でなければなりません）。i 番目の広告パネルを設置した場合、集客効果 b_i が得られます。設置しなかったパネルからは集客効果は得られません。

広告パネル同士は重なって配置することはできません。すなわち、設置された異なる 2 つの広告パネルが同じスロットを同時に占有することはできません。重ならない限り、隣接して配置することは問題ありません。

選んだ広告パネルの配置が決まると、どの広告パネルにも占有されていないスロットが 空きスロット となります。1 枚も設置しない場合は、すべてのスロットが空きスロットです。

この廊下には防災上の規定があります。廊下の壁面には一定間隔で避難誘導灯が設置されており、空きスロットが長く続く区間では、来場者が誘導灯に注意を向けにくくなるおそれがあります。そのため、以下の 防災規定 を満たさなければなりません：

廊下上で空きスロットが K 個以上連続して存在してはならない。すなわち、連続する空きスロットからなる極大な区間の長さは、どの箇所においても K-1 以下でなければならない。

この制約は廊下の両端付近にも適用されます。例えば、最も左に設置された広告パネルの左端がスロット s であるとき、スロット 1 からスロット s-1 まではすべて空きスロットであり、これらは連続する s-1 個の空きスロットとなるため、s - 1 \leq K - 1 でなければなりません。同様に、最も右に設置された広告パネルの右端がスロット t であるとき、スロット t+1 からスロット L までの L-t 個の連続する空きスロットについても L - t \leq K - 1 でなければなりません。

広告パネルを 1 枚も設置しない場合は、スロット 1 からスロット L までの L 個すべてが連続する空きスロットとなります。したがって、L \leq K - 1（すなわち L < K）のときに限り、1 枚も設置しない配置は防災規定を満たします。このとき集客効果の合計は 0 です。

高橋君は、防災規定を満たしつつ、設置した広告パネルの集客効果の合計を最大化したいと考えています。

防災規定を満たすような広告パネルの選び方と配置が 1 つ以上存在するならば、集客効果の合計の最大値を出力してください。防災規定を満たす配置が 1 つも存在しない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 400
  • 1 \leq L \leq 1000
  • 1 \leq K \leq L
  • 1 \leq w_i \leq L （1 \leq i \leq N）
  • 1 \leq b_i \leq 10^6 （1 \leq i \leq N）
  • 入力はすべて整数である。

入力

N L K
w_1 b_1
w_2 b_2
\vdots
w_N b_N
  • 1 行目には、広告パネルの候補の枚数 N、廊下の全長 L、空きスロットの連続個数の上限に関する値 K が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各広告パネルの情報が与えられる。1 + i 行目（1 \leq i \leq N）には、i 番目の広告パネルが占有するスロット数 w_i と集客効果 b_i がスペース区切りで与えられる。

出力

防災規定を満たす配置が存在する場合は、集客効果の合計の最大値を 1 行で出力せよ。存在しない場合は -1 を 1 行で出力せよ。

入力例 1

4 8 3
2 5
3 8
1 2
4 7

出力例 1

17

入力例 2

3 5 1
2 10
4 20
4 30

出力例 2

-1

入力例 3

12 30 5
3 12
7 25
4 14
6 18
2 7
5 16
8 30
1 3
9 28
4 13
10 35
6 20

出力例 3

109

入力例 4

30 100 7
5 120
12 260
7 150
20 500
3 60
15 330
8 180
10 210
6 140
25 620
4 90
18 410
9 200
11 240
13 290
2 45
16 370
14 310
7 170
5 115
22 540
19 430
1 20
30 750
6 135
10 230
17 390
8 175
24 580
12 255

出力例 4

2475

入力例 5

1 1 1
1 100

出力例 5

100

Score : 400 pts

Problem Statement

Takahashi has been assigned the task of placing advertisement panels along a long corridor in an exhibition hall. The corridor is divided into slots every 1 meter, with a total length of L meters. That is, slots 1, 2, \ldots, L are lined up in a row.

Takahashi has N advertisement panels as candidates. All N advertisement panels are distinct, and he can independently choose whether or not to install each one. Each panel can be installed at most once, and if installed, it can be freely placed at any position along the corridor (as long as the constraints described below are satisfied). There are no constraints based on the order of placement or panel numbering.

The i-th advertisement panel (1 \leq i \leq N) occupies w_i consecutive slots. Specifically, if the i-th advertisement panel is installed with its left edge aligned to slot s, it occupies slots s, s+1, \ldots, s+w_i-1 (where 1 \leq s and s + w_i - 1 \leq L must hold). If the i-th advertisement panel is installed, it provides an attraction effect of b_i. Panels that are not installed provide no attraction effect.

Advertisement panels cannot overlap each other. That is, two different installed advertisement panels cannot occupy the same slot simultaneously. As long as they do not overlap, placing them adjacent to each other is acceptable.

Once the placement of the chosen advertisement panels is determined, any slot not occupied by any advertisement panel becomes a vacant slot. If no panels are installed, all slots are vacant slots.

This corridor has fire safety regulations. Emergency guidance lights are installed at regular intervals on the corridor walls, and in sections where vacant slots continue for a long stretch, there is a concern that visitors may not pay attention to the guidance lights. Therefore, the following fire safety regulation must be satisfied:

There must not be K or more consecutive vacant slots on the corridor. That is, the length of any maximal interval of consecutive vacant slots must be K-1 or less at every location.

This constraint also applies near both ends of the corridor. For example, if the left edge of the leftmost installed advertisement panel is at slot s, then slots 1 through s-1 are all vacant slots, forming s-1 consecutive vacant slots, so s - 1 \leq K - 1 must hold. Similarly, if the right edge of the rightmost installed advertisement panel is at slot t, then the L-t consecutive vacant slots from slot t+1 to slot L must also satisfy L - t \leq K - 1.

If no advertisement panels are installed, all L slots from slot 1 to slot L are consecutive vacant slots. Therefore, a placement with no panels installed satisfies the fire safety regulation only when L \leq K - 1 (i.e., L < K). In this case, the total attraction effect is 0.

Takahashi wants to maximize the total attraction effect of the installed advertisement panels while satisfying the fire safety regulation.

If there exists at least one way to select and place advertisement panels that satisfies the fire safety regulation, output the maximum total attraction effect. If no placement satisfying the fire safety regulation exists, output -1.

Constraints

  • 1 \leq N \leq 400
  • 1 \leq L \leq 1000
  • 1 \leq K \leq L
  • 1 \leq w_i \leq L (1 \leq i \leq N)
  • 1 \leq b_i \leq 10^6 (1 \leq i \leq N)
  • All input values are integers.

Input

N L K
w_1 b_1
w_2 b_2
\vdots
w_N b_N
  • The first line contains the number of candidate advertisement panels N, the total length of the corridor L, and the value K related to the upper limit on the number of consecutive vacant slots, separated by spaces.
  • From the 2nd line to the (N + 1)-th line, information about each advertisement panel is given. The (1 + i)-th line (1 \leq i \leq N) contains the number of slots w_i occupied by the i-th advertisement panel and its attraction effect b_i, separated by spaces.

Output

If a placement satisfying the fire safety regulation exists, output the maximum total attraction effect in one line. If no such placement exists, output -1 in one line.

Sample Input 1

4 8 3
2 5
3 8
1 2
4 7

Sample Output 1

17

Sample Input 2

3 5 1
2 10
4 20
4 30

Sample Output 2

-1

Sample Input 3

12 30 5
3 12
7 25
4 14
6 18
2 7
5 16
8 30
1 3
9 28
4 13
10 35
6 20

Sample Output 3

109

Sample Input 4

30 100 7
5 120
12 260
7 150
20 500
3 60
15 330
8 180
10 210
6 140
25 620
4 90
18 410
9 200
11 240
13 290
2 45
16 370
14 310
7 170
5 115
22 540
19 430
1 20
30 750
6 135
10 230
17 390
8 175
24 580
12 255

Sample Output 4

2475

Sample Input 5

1 1 1
1 100

Sample Output 5

100