/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
問題文
ある大学では N 個の科目が開講されています。i 番目の科目は履修するのに必要な労力が a_i で、時間割上で b_i 番目の時間に講義が行われ、履修すると c_i 単位を取得できます。
あなたはこれらの科目からいくつかを履修して合計で M 単位以上を取得する必要があります。ただし、時間割上で同じ時間に講義が行われる科目を同時に履修することはできません。
M 単位以上を取得することができるならばそのために必要な労力の合計の最小値を、できないならば -1 を出力してください。
制約
- 1 \leq N, M \leq 5000
- 1 \leq a_i,b_i,c_i \leq 5000
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 c_1 \vdots a_N b_N c_N
出力
M 単位以上を取得することができるならばそのために必要な労力の合計の最小値を、できないならば -1 を出力せよ。
入力例 1
3 4 3 1 2 4 1 2 5 2 2
出力例 1
8
1,3 番目の科目を履修すると、必要な労力の合計が 8 になります。これが最小値です。
なお、1,2 番目の科目は同じ時間に講義が行われるので同時に履修することができません。
入力例 2
3 100 1 100 1 1 200 1 1 300 1
出力例 2
-1
すべての科目を履修しても 100 単位以上を取得することができません。
入力例 3
2 100 10 5 99 10 5 99
出力例 3
-1
2 つの科目は同じ時間に講義が行われるので同時に履修することができず、100 単位以上を取得することができません。
入力例 4
10 522 4575 1426 4445 3772 81 3447 629 3497 2202 2775 4325 3982 4784 3417 2156 1932 902 728 3537 3857 739 1918 4211 4679 3506 3340 1568 1868 16 2940
出力例 4
629
Problem Statement
There are N courses in a university. The i-th course requires an effort of a_i, is scheduled at the b_i-th time slot, and counts for c_i credits.
You need to take some of the courses to earn a total of M credits. However, you cannot take multiple courses scheduled at the same time slot.
If you can earn M or more credits, print the minimum total effort required to do so; otherwise, print -1.
Constraints
- 1 \leq N, M \leq 5000
- 1 \leq a_i,b_i,c_i \leq 5000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M a_1 b_1 c_1 \vdots a_N b_N c_N
Output
If you can earn M or more credits, print the minimum total effort required to do so; otherwise, print -1.
Sample Input 1
3 4 3 1 2 4 1 2 5 2 2
Sample Output 1
8
If you take the 1-st and 3-rd courses, the total effort required is 8, which is the minimum.
Note that you cannot take both the 1-st and 2-nd courses, because they are scheduled at the same slot.
Sample Input 2
3 100 1 100 1 1 200 1 1 300 1
Sample Output 2
-1
Even if you take all the courses, you cannot earn 100 or more credits.
Sample Input 3
2 100 10 5 99 10 5 99
Sample Output 3
-1
The two courses are scheduled at the same time slot, so you cannot earn 100 or more credits.
Sample Input 4
10 522 4575 1426 4445 3772 81 3447 629 3497 2202 2775 4325 3982 4784 3417 2156 1932 902 728 3537 3857 739 1918 4211 4679 3506 3340 1568 1868 16 2940
Sample Output 4
629