H - Course Registration Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

ある大学では 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