402191: GYM100694 A Did he drop any good loot?

Slava plays a very cool RPG. He has just cleaned up the dungeon, and n cool artifacts have been dropped down. He wants to sell them to gain as much profit as he can. Each artifact has its own price p_i and weight w_i. Slava cannot carry artifacts with the total weight greater than m, but it's possible to activate some of them. Being activated, the i-th artifact increases Slava's strength and adds additional weight d_i to Slava's weight limit. Activated artifacts don't disappear, their price and weight don't change and they still can be sold. Slava can activate no more than 2 artifacts at the same time.

More formally, Slava wants to choose a set of artifacts with the greatest total price among all correct sets. The set of artifacts i₁, i₂, ..., i_k (k ≤ n) is called correct if w_i1 + w_i2 + ... + w_ik ≤ m + s, where s is the additional weight limit gained from the actifacts activation: s = d_j1 + d_j2, if Slava activated artifacts j₁ and j₂ (j₁ ≠ j₂), s = d_j — if he activated only artifact j, and s = 0, if he didn't activate any artifacts (j₁, j₂ and j must be contained in the set of chosen artifacts i₁, i₂, ..., i_k).

The first line contains two space-separated integers n and m (1 ≤ n ≤ 10⁴, 1 ≤ m ≤ 500) — the number of artifacts and the Slava's weight limit.

Each of the next n lines contains three space-separated integers p_i, w_i and d_i (1 ≤ p_i ≤ 10⁵, 1 ≤ w_i ≤ 100, 0 ≤ d_i ≤ 100) — the price of the i-th artifact, its weight and the additional weight limit it gains at its activation.

Write one integer — the maximum total price of the artifacts Slava can take with him.

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

15

3 10
100 100 20
200 80 30
300 60 40

0

In the first sample Slava cannot just take all artifacts — his weight limit is 10, and the total weight of all artifacts is 15. That's why he activates artifacts 1 and 4, which leads to increasing his weight limit to 10 + 3 + 4 = 17 (in fact, he can activate any pair of artifacts which increases his weight limit by 5 or more).

In the second sample Slava cannot take any artifacts, either with the activation or without it.