Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

As one of the most powerful brushes in the world, zhx usually takes part in all kinds of contests.

One day, zhx takes part in an contest. He found the contest very easy for him.

There are $n$ problems in the contest. He knows that he can solve the $i^{th}$ problem in $t_i$ units of time and he can get $v_i$ points.

As he is too powerful, the administrator is watching him. If he finishes the $i^{th}$ problem before time $l_i$, he will be considered to cheat.

zhx doesn't really want to solve all these boring problems. He only wants to get no less than $w$ points. You are supposed to tell him the minimal time he needs to spend while not being considered to cheat, or he is not able to get enough points.

Note that zhx can solve only one problem at the same time. And if he starts, he would keep working on it until it is solved. And then he submits his code in no time.

One day, zhx takes part in an contest. He found the contest very easy for him.

There are $n$ problems in the contest. He knows that he can solve the $i^{th}$ problem in $t_i$ units of time and he can get $v_i$ points.

As he is too powerful, the administrator is watching him. If he finishes the $i^{th}$ problem before time $l_i$, he will be considered to cheat.

zhx doesn't really want to solve all these boring problems. He only wants to get no less than $w$ points. You are supposed to tell him the minimal time he needs to spend while not being considered to cheat, or he is not able to get enough points.

Note that zhx can solve only one problem at the same time. And if he starts, he would keep working on it until it is solved. And then he submits his code in no time.

Multiply test cases(less than $50$). Seek $EOF$ as the end of the file.

For each test, there are two integers $n$ and $w$ separated by a space. ($1 \leq n \leq 30$, $0 \leq w \leq {10}^{9}$)

Then come n lines which contain three integers $t_i, v_i, l_i$. ($1 \leq t_i,l_i \leq {10}^{5}, 1 \leq v_i \leq {10}^{9}$)

For each test, there are two integers $n$ and $w$ separated by a space. ($1 \leq n \leq 30$, $0 \leq w \leq {10}^{9}$)

Then come n lines which contain three integers $t_i, v_i, l_i$. ($1 \leq t_i,l_i \leq {10}^{5}, 1 \leq v_i \leq {10}^{9}$)

提交代码