Problem F
Packing Equipment

Ty is trying to pack as many pieces of useful equipment as possible for his upcoming trip. Unfortunately, with his horrible shopping habits, he’s ended up buying multiple tools that serve the same functions.

Each tool on its own only serves one specific function which will be represented by an integer $f$. Tools can also be either multi-use or single-use. Multi-use tools can be used as many times as needed, while single-use tools can only be used once before breaking. To indicate the type of tool and the function it serves, each tool is assigned a type number $t$ based on the following:

• If the tool is a multi-use tool with function $f$, then it will be assigned the type number $t=2f$.

• If the tool is a single-use tool with function $f$, then it will be assigned the type number $t=2f + 1$.

Each tool also has an associated weight value $w$ and utility value $u$.

If Ty packs a multi-use tool with function $f$, he will not pack any other tools with the same function as that would be redundant. However, if he packs a single-use tool with function $f$, he may still pack more single-use tools with the same function. He may also choose not to pack any tools with function $f$ at all in hopes that he won’t need it.

Although Ty is super strong, he is still human and can only carry a maximum weight of $m$.

Given the type, weight, and utility values of each tool Ty has bought, along with the maximum weight he can carry, what is the maximum total utility Ty can pack without any redundancy and without exceeding his maximum carry weight?

Input

The first line of input contains two integers: the number of tools that Ty has bought $n$ ($1 \leq n \leq 10^3$) and the maximum weight that Ty can carry $m$ ($1 \leq m \leq 10^3$).

The next $n$ lines each describe an item, containing three integers each: the type of the item $t_i$ ($0 \leq t_i \leq 10^6$), the weight of the item $w_i$ ($1 \leq w_i \leq 10^3$), and the utility value of the item $u_i$ ($1 \leq u_i \leq 10^6$).

Output

Print the maximum total utility Ty can pack without any redundancy and without exceeding his maximum carry weight.

4 3
1 1 3
1 1 3
1 1 3
1 1 3

9

4 5
0 1 3
0 1 4
1 1 2
1 1 3

5

4 5
0 1 3
1 2 3
2 3 4
3 4 5

8