E - Vitamin Balance 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 450 点

問題文

N 個の食べ物があり、それぞれの食べ物にはビタミン 1,2,3 のうちちょうど 1 つのみが含まれています。
具体的には、i 個目の食べ物を食べると、ビタミン V_i が A_i だけ摂取でき、またカロリーが C_i だけ摂取されます。

高橋君は、摂取するカロリーが合計で X 以下となるように、N 個の食べ物のうちいくつか（0 個でも良い）を選んで食べることができます。
このとき、「ビタミン 1,2,3 のうちもっとも摂取量が少ないものの摂取量」としてあり得る最大の値を求めてください。

制約

  • 1\leq N \leq 5000
  • 1\leq X \leq 5000
  • 1\leq V_i\leq 3
  • 1\leq A_i\leq 2\times 10^5
  • 1\leq C_i\leq X
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N X
V_1 A_1 C_1
V_2 A_2 C_2
\vdots
V_N A_N C_N

出力

高橋君が摂取カロリーの合計が X 以下となるように食べ物を食べたとき、「ビタミン 1,2,3 のうちもっとも摂取量が少ないものの摂取量」としてあり得る最大の値を出力せよ。

入力例 1

5 25
1 8 5
2 3 5
2 7 10
3 2 5
3 3 10

出力例 1

3

それぞれの食べ物を食べると高橋君は次のものを摂取します。

  • 1 個目の食べ物を食べると、ビタミン 1 を 8 とカロリーを 5 だけ摂取する。
  • 2 個目の食べ物を食べると、ビタミン 2 を 3 とカロリーを 5 だけ摂取する。
  • 3 個目の食べ物を食べると、ビタミン 2 を 7 とカロリーを 10 だけ摂取する。
  • 4 個目の食べ物を食べると、ビタミン 3 を 2 とカロリーを 5 だけ摂取する。
  • 5 個目の食べ物を食べると、ビタミン 3 を 3 とカロリーを 10 だけ摂取する。

高橋君が 1, 2, 4, 5 個目の食べ物を食べると、 高橋君はビタミン 1 を 8、ビタミン 2 を 3、ビタミン 3 を 5、そしてカロリーを 25 だけ摂取します。
このとき、「ビタミン 1,2,3 のうちもっとも摂取量が少ないもの」はビタミン 2 であり、その摂取量は 3 です。

どのように食べ物を選んで食べても、摂取カロリーの合計が 25 以下となるようにビタミン 1,2,3 すべてを 4 以上摂取することはできないため、3 を出力します。

入力例 2

2 5000
1 200000 1
2 200000 1

出力例 2

0

Score : 450 points

Problem Statement

There are N foods, each containing exactly one of vitamins 1, 2, and 3.
Specifically, eating the i-th food gives you A_i units of vitamin V_i, and C_i calories.

Takahashi can choose any subset of these N foods as long as the total calorie consumption does not exceed X.
Find the maximum possible value of this: the minimum intake among vitamins 1, 2, and 3.

Constraints

  • 1 \leq N \leq 5000
  • 1 \leq X \leq 5000
  • 1 \leq V_i \leq 3
  • 1 \leq A_i \leq 2 \times 10^5
  • 1 \leq C_i \leq X
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N X
V_1 A_1 C_1
V_2 A_2 C_2
\vdots
V_N A_N C_N

Output

Print the maximum possible value of "the minimum intake among vitamins 1, 2, and 3" when the total calories consumed is at most X.

Sample Input 1

5 25
1 8 5
2 3 5
2 7 10
3 2 5
3 3 10

Sample Output 1

3

Each food provides the following if eaten:

  • 1st food: 8 units of vitamin 1, and 5 calories
  • 2nd food: 3 units of vitamin 2, and 5 calories
  • 3rd food: 7 units of vitamin 2, and 10 calories
  • 4th food: 2 units of vitamin 3, and 5 calories
  • 5th food: 3 units of vitamin 3, and 10 calories

Eating the 1st, 2nd, 4th, and 5th foods gives 8 units of vitamin 1, 3 units of vitamin 2, 5 units of vitamin 3, and 25 calories.
In this case, the minimum among the three vitamin intakes is 3 (vitamin 2).

It is impossible to get 4 or more units of each vitamin without exceeding 25 calories, so the answer is 3.

Sample Input 2

2 5000
1 200000 1
2 200000 1

Sample Output 2

0