K - Deadline
問題文
限界開発者である寺子さんは、現在 $N$ 個のタスクを抱えており、精神的・体力的な限界を迎えています。
これから $3$ つの締め切り $S_1, S_2, S_3$ が順番に訪れます。
それぞれの締め切りは、現在時刻 $0$ から見て $T_1, T_2, T_3$ 分後です（$T_1 \le T_2 \le T_3$）。
各タスク $i$ ($1 \leq i \leq N$) には、以下の3つの情報が与えられます：
-
所要時間 $C_i$：完了するのにかかる時間。
-
重要度 $V_i$：完了した際に得られるスコア。
-
区分 $K_i$：どの締め切りに関連するタスクか（$1, 2, 3$ のいずれか）。
寺子さんはいくつかのタスクを諦め合計スコアを最大化することにしました。合計スコアはこなしたタスクのの重要度 $V_i$ の総和です。以下の条件を満たすようにタスクをこなした時の合計スコアを最大化してください。
-
区分 1 のタスクは時刻 $T_1$ の時点で、完了していなければスコアは獲得できません。
-
区分 2 のタスクは時刻 $T_2$ の時点で、完了していなければスコアは獲得できません。
-
区分３ のタスクは時刻 $T_3$ の時点で、完了していなければスコアは獲得できません。
ただし、タスクは同時に一つしかできません。また、タスクが終了すると同時に新しいタスクを開始できます。
制約
- $1\le N\le 100$
- $1\le T_1\le T_2\le T_3\le 10^5$
- $1\le C_i\le 100$
- $1\le V_i\le 10^5$
- $K_i \in {1, 2, 3}$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
$T_1~~T_2$$~~T_3$
$C_1~~V_1$$~~K_1$
$C_2~~V_2$$~~K_2$
$\vdots$
$C_n~~V_n$$~~K_n$
出力
ありえるスコアの最大値を出力せよ。
4
10 20 40
8 50 1
15 70 2
15 80 2
25 100 3
180
最初に3番目のタスクを行い、残りの25分で4番目のタスクを行った時、スコアが180となり、これが最大です。
3
30 60 90
30 30 1
30 30 2
30 30 3
90
全てのタスクを実行できる時もあります。
3
1 2 3
10 100 1
20 200 2
30 300 3
0
一つもタスクを実行できないこともあります。
3
10 20 30
20 100 3
9 100 1
1 100 1
300
例えば、タスクを $2 \to 3 \to 1$ の順に実行することで全てのタスクを完了できます。