题目描述

小达正在锻炼自己的三项战斗属性：力量、敏捷和智力。

有 $n$ 种训练项目，每种项目恰好只提升其中一种属性。

具体来说，进行第 $i$ 种训练时，可以提升对应属性 $v_i$（$1$ 表示力量，$2$ 表示敏捷，$3$ 表示智力）的经验值 $a_i$，同时消耗体力 $c_i$。

小达可以自由选择若干种训练项目（也可以什么都不做），但总消耗的体力不能超过 $x$。

他希望在体力允许的范围内，让自己的三项属性中最弱的一项尽可能高。

请计算：在总消耗体力不超过 $x$ 的条件下，三项属性经验值的最小值最大可以是多少。

输入格式

第一行两个整数 $n$ 和 $x$，表示训练项目的数量和总体力消耗限制。

接下来 $n$ 行，每行 $3$ 个整数 $v_i,\ a_i,\ c_i$，分别表示第 $i$ 种训练项目的属性类别、提升的经验值和消耗的体力。

输出格式

输出在总消耗体力不超过 $x$ 的条件下，三项属性经验值的最小值的最大可能值。

样例

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

3

2 5000
1 200000 1
2 200000 1

0

样例1解释

各训练项目的效果如下：

• 项目 $1$：提升力量 $8$，消耗体力 $5$
• 项目 $2$：提升敏捷 $3$，消耗体力 $5$
• 项目 $3$：提升敏捷 $7$，消耗体力 $10$
• 项目 $4$：提升智力 $2$，消耗体力 $5$
• 项目 $5$：提升智力 $3$，消耗体力 $10$

若小达选择项目 $1$、$2$、$4$、$5$，总消耗体力为 $5+5+5+10=25$，三项属性经验值分别为：力量 $8$，敏捷 $3$，智力 $5$。此时最弱的一项是敏捷的 $3$。

无法在总消耗体力 $\le 25$ 的条件下，让三项属性经验值都达到 $4$ 或以上，因此输出 $3$。

数据范围

对于 $30\%$ 的数据，$1\le n\le 20$。

对于另外 $20\%$ 的数据，$1 \le n \le 5000$，$1 \le x \le 5000$，$1\le v_i\le 3$，$1\le a_i\le 2\times10^5$，$c_i=1$。

对于 $100\%$ 的数据，$1 \le n \le 5000$，$1 \le x \le 5000$，$1\le v_i\le 3$，$1\le a_i\le 2\times10^5$，$1\le c_i\le x$。