「吼，死了啦，都你害我沒打到boss。」

「這個冰凍球，就是遜啦。」

彬彬和阿瑋今天又到網咖玩碰碰法師了，然而他們實在是太遜了，每次都過不了關。

杰哥在旁邊看到正在玩碰碰法師的兩人，很同情他們過了一整天還在打同一關。

杰哥除了能讓人「轉大人」之外，還可以讓遊戲中的球「轉大球」，增加球的傷害。

不過為了不讓彬彬和阿瑋發現他的超能力，他每次都只會讓球的傷害剛好能通過該個關卡。

請你幫忙杰哥，告訴他需要增加球的傷害至多少。

此題中碰碰法師的遊玩規則：對於一個回合，

1. 怪物出現

2. 英雄對目前場面上存在的所有怪物造成 \(x\) 點傷害，如果怪物血量 \(\le 0\)，則該怪物死亡，不再重生。

3. 剩餘場面上血量大於 \(0\) 的怪物會執行它們的技能：豌豆射手會對英雄造成 \(1\) 滴血的傷害；牧師則會幫場面上所有存活的怪物回復 \(1\) 滴血，其中所有怪物回復的最大血量為起始血量，若回復血量超過起始血量，則僅會回復至起始血量。

關卡通過若且唯若所有怪物皆死亡且英雄血量 \(> 0\)；通關失敗若且唯若英雄血量 \(\leq 0\) 或無法將所有怪物清除。

Input

第一行包含兩個整數 \(n, k\) ， \(n\) 代表該關卡的怪物數目， \(k\) 代表操作者的初始血量。

\(1\le n\le 10^5, 1\le k\le 10^3\)

接下來 \(n\) 行，每行包含三個數 \(c_i, t_i, h_i\) ，分別代表第 \(i\) 個怪物種類，怪物出現的回合，以及怪物的血量，怪物出現後就不會主動消失。

\(c_i= 1, 2\)

\(1\le t_i\le n\)

\(1\le h_i\le 10^9\)

若 \(c_i\) 為 \(1\) ，則代表該個怪物為豌豆射手；若 \(c_i\) 為 \(2\) ，則代表該個怪物為牧師。

Output

輸出 \(1\) 行，包含一個整數，代表可以讓彬彬和阿瑋通關的球的傷害 \(x\) 的最小值。

Constraints

第 \(1\) 組測資, \(n\le 200\) 且 \(c_i=1\)。\((18\text{%})\)

第 \(2\) 組測資, \(n\le 200\)。\((17\text{%})\)

第 \(3\) 組測資, \(c_i=1\)。\((23\text{%})\)

第 \(4\) 組測資, 沒有其他限制。\((42\text{%})\)

Sample Input 1

12 10
1 1 10
1 2 10
1 10 5
1 10 7
1 10 9
1 10 11
1 10 13
1 10 15
1 10 17
1 10 19
1 10 21
1 10 23

Sample Output 1

10

Sample Input 2

6 10
1 1 20
2 1 10
1 3 30
2 3 20
1 5 20
2 5 20

Sample Output 2

7

Notes

做不出來的就要去杰哥家喔