碰碰法師
「吼,死了啦,都你害我沒打到boss。」
「這個冰凍球,就是遜啦。」
彬彬和阿瑋今天又到網咖玩碰碰法師了,然而他們實在是太遜了,每次都過不了關。
杰哥在旁邊看到正在玩碰碰法師的兩人,很同情他們過了一整天還在打同一關。
杰哥除了能讓人「轉大人」之外,還可以讓遊戲中的球「轉大球」,增加球的傷害。
不過為了不讓彬彬和阿瑋發現他的超能力,他每次都只會讓球的傷害剛好能通過該個關卡。
請你幫忙杰哥,告訴他需要增加球的傷害至多少。
此題中碰碰法師的遊玩規則:對於一個回合,
怪物出現
英雄對目前場面上存在的所有怪物造成 \(x\) 點傷害,如果怪物血量 \(\le 0\),則該怪物死亡,不再重生。
剩餘場面上血量大於 \(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
做不出來的就要去杰哥家喔
Comments