D - Job Selection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君はフリーランスのプログラマーで、複数の仕事の依頼を受けています。現在 N 件の仕事の候補があり、高橋君は 1 日目から M 日目までの M 日間の期間内でこれらの仕事に取り組むことができます。この期間外（M+1 日目以降）に作業を行うことはできません。

各仕事 i（ 1 \leq i \leq N ）には以下の情報が与えられます：

  • 完了に必要な日数 D_i
  • 完了時に得られる報酬 V_i
  • 納期 T_i

高橋君は同時に 1 つの仕事しかこなせず、各仕事は最大 1 回しか引き受けられません。ある仕事に取りかかったら、途中で中断することはできず、 D_i 日間連続で作業する必要があります。仕事 i を s 日目（ s \geq 1 ）に開始した場合、 s, s+1, \ldots, s + D_i - 1 日目に作業を行い、 s + D_i - 1 日目に完了となります。次の仕事は最も早くて s + D_i 日目から開始できます。

仕事 i を引き受ける場合、納期 T_i 日目までに完了しなければなりません。すなわち、開始日を s としたとき、 s + D_i - 1 \leq T_i を満たす必要があります。制約より T_i \leq M が保証されているため、納期を守れば作業は自動的に M 日間の期間内に収まります。

高橋君は N 件の候補から仕事の部分集合を選び、選んだ仕事すべてをそれぞれの納期以内に完了できるように作業順序とスケジュールを決めます。仕事を一つも引き受けないことも可能で、その場合の報酬の合計は 0 です。

また、特別なルールがあります。高橋君が完了した仕事の数が K 個以上のとき、クライアントからの信頼ボーナスとして追加で B が得られます。このボーナスは条件を満たせば一度だけ加算され、完了した仕事が K 個以上であれば何個であっても加算額は B で一定です。

高橋君が最終的に得る報酬は、完了した仕事の報酬 V_i の総和に、ボーナス条件を満たしていれば B を加えたものです。引き受ける仕事の集合とその作業順序を適切に選ぶことで、この最終的な報酬の最大値を求めてください。

制約

  • 1 \leq N \leq 200
  • 1 \leq M \leq 5000
  • 1 \leq K \leq N
  • 0 \leq B \leq 10^9
  • 1 \leq D_i \leq M
  • 1 \leq V_i \leq 10^9
  • 1 \leq T_i \leq M
  • 入力はすべて整数

入力

N M K B
D_1 V_1 T_1
D_2 V_2 T_2
\vdots
D_N V_N T_N
  • 1 行目には、仕事の候補数を表す N 、期間の日数を表す M 、ボーナス条件の仕事数を表す K 、ボーナスの値を表す B が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各仕事の情報が N 行で与えられる。
  • 1 + i 行目では、仕事 i の完了に必要な日数 D_i 、報酬 V_i 、納期 T_i がスペース区切りで与えられる。

出力

得られる報酬の合計（ボーナスを含む）の最大値を 1 行で出力せよ。

入力例 1

4 7 2 10
2 50 3
3 70 5
1 20 2
2 40 7

出力例 1

170

入力例 2

3 3 3 100
2 30 2
2 40 3
1 10 1

出力例 2

50

入力例 3

10 30 5 200
3 80 5
5 120 12
2 50 6
7 200 20
4 90 15
6 150 18
1 20 3
8 300 30
3 70 10
5 110 25

出力例 3

1060

入力例 4

25 100 12 1000
4 120 10
8 260 20
3 90 12
10 400 35
6 180 25
12 500 50
5 150 30
7 230 40
2 60 15
9 310 55
11 450 70
4 140 45
6 210 60
13 520 85
3 100 33
15 700 100
5 170 65
8 280 75
1 30 22
10 360 90
6 190 48
7 240 58
14 600 95
2 80 38
9 330 82

出力例 4

5060

入力例 5

1 1 1 1000000000
1 1000000000 1

出力例 5

2000000000

Score : 400 pts

Problem Statement

Takahashi is a freelance programmer who has received multiple job requests. Currently there are N job candidates, and Takahashi can work on these jobs within a period of M days from day 1 to day M. He cannot perform any work outside this period (from day M+1 onwards).

For each job i (1 \leq i \leq N), the following information is given:

  • Number of days required to complete: D_i
  • Reward upon completion: V_i
  • Deadline: T_i

Takahashi can only work on 1 job at a time, and each job can be accepted at most once. Once he starts a job, he cannot interrupt it and must work on it for D_i consecutive days. If job i is started on day s (s \geq 1), he works on days s, s+1, \ldots, s + D_i - 1, and the job is completed on day s + D_i - 1. The next job can be started at the earliest on day s + D_i.

If job i is accepted, it must be completed by the deadline day T_i. That is, if the starting day is s, the condition s + D_i - 1 \leq T_i must be satisfied. Since the constraints guarantee T_i \leq M, meeting the deadline automatically ensures the work falls within the M-day period.

Takahashi selects a subset of jobs from the N candidates and determines the work order and schedule so that all selected jobs can be completed within their respective deadlines. It is also possible to accept no jobs at all, in which case the total reward is 0.

Additionally, there is a special rule. When the number of jobs Takahashi has completed is K or more, he receives an additional trust bonus of B from the clients. This bonus is added only once if the condition is met, and regardless of how many jobs are completed (as long as it is K or more), the bonus amount is a fixed B.

Takahashi's final reward is the sum of the rewards V_i of all completed jobs, plus B if the bonus condition is satisfied. Find the maximum value of this final reward by appropriately choosing the set of jobs to accept and their work order.

Constraints

  • 1 \leq N \leq 200
  • 1 \leq M \leq 5000
  • 1 \leq K \leq N
  • 0 \leq B \leq 10^9
  • 1 \leq D_i \leq M
  • 1 \leq V_i \leq 10^9
  • 1 \leq T_i \leq M
  • All inputs are integers

Input

N M K B
D_1 V_1 T_1
D_2 V_2 T_2
\vdots
D_N V_N T_N
  • The first line contains N representing the number of job candidates, M representing the number of days in the period, K representing the number of jobs required for the bonus condition, and B representing the bonus value, separated by spaces.
  • From the 2nd line to the (N+1)-th line, the information for each job is given over N lines.
  • The (1+i)-th line contains the number of days D_i required to complete job i, the reward V_i, and the deadline T_i, separated by spaces.

Output

Output the maximum total reward (including the bonus) in a single line.

Sample Input 1

4 7 2 10
2 50 3
3 70 5
1 20 2
2 40 7

Sample Output 1

170

Sample Input 2

3 3 3 100
2 30 2
2 40 3
1 10 1

Sample Output 2

50

Sample Input 3

10 30 5 200
3 80 5
5 120 12
2 50 6
7 200 20
4 90 15
6 150 18
1 20 3
8 300 30
3 70 10
5 110 25

Sample Output 3

1060

Sample Input 4

25 100 12 1000
4 120 10
8 260 20
3 90 12
10 400 35
6 180 25
12 500 50
5 150 30
7 230 40
2 60 15
9 310 55
11 450 70
4 140 45
6 210 60
13 520 85
3 100 33
15 700 100
5 170 65
8 280 75
1 30 22
10 360 90
6 190 48
7 240 58
14 600 95
2 80 38
9 330 82

Sample Output 4

5060

Sample Input 5

1 1 1 1000000000
1 1000000000 1

Sample Output 5

2000000000