/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
ある忍者が N 体の魔物と一体ずつ順番に戦います。i 番目の魔物の攻撃力は a_i、体力は b_i であり、魔物は体力が 0 以下になった瞬間に倒れます。
なお、魔物は地上にいるか飛んでいるかのどちらかであり、x_i = 0 なら i 番目の魔物は地上におり、x_i = 1 なら飛んでいます。
忍者は初め、M 枚の手裏剣を持っています。それぞれの手裏剣は一度投げると二度と使えません。
忍者と i 番目の魔物は以下のように戦います。
- まず、忍者が持っている手裏剣から 0 枚以上を選んで魔物に投げる。投げた枚数だけ魔物の体力が減り、飛んでいる魔物に 1 枚以上の手裏剣を投げた場合、その魔物は地上に降りる。
- その後、忍者と魔物が交互に相手を攻撃する。忍者の攻撃により魔物の体力は 1 減り、魔物の攻撃により忍者の体力は a_i 減る。なお、魔物が地上にいるなら忍者が先に攻撃し、飛んでいるなら魔物が先に攻撃する。
忍者の最初の体力と、全ての魔物を倒し終わった後の体力の差としてあり得る最小値を求めてください。
なお、忍者の体力は十分に大きいとします。
制約
- 1 \leq N \leq 3 \times 10^5
- 0 \leq M \leq 10^{11}
- 1 \leq a_i, b_i \leq 3 \times 10^5
- x_i = 0 または x_i = 1
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 x_1 a_2 b_2 x_2 \vdots a_N b_N x_N
出力
答えを出力せよ。
入力例 1
2 1 2 2 1 5 2 0
出力例 1
4
忍者が以下のように戦うと、忍者の体力は合計で 4 減少し、これが最適です。
- 1 番目の魔物には手裏剣を投げない。
- 魔物は飛んでいるので、魔物が先に忍者を攻撃する。忍者の体力が 2 減る。
- 忍者が攻撃する。魔物の体力が 1 になる。
- 魔物が攻撃する。忍者の体力が 2 減る。
- 忍者が攻撃する。魔物は体力が 0 になり、倒れる。
- 2 番目の魔物に手裏剣を 1 枚投げる。魔物の体力は 1 になる。
- 魔物は地上にいるので、忍者が先に魔物を攻撃する。魔物は体力が 0 になり、倒れる。
入力例 2
1 2 1 4 1
出力例 2
1
忍者が以下のように戦うと、忍者の体力は合計で 1 減少し、これが最適です。
- 1 番目の魔物に手裏剣を 2 枚投げる。魔物の体力は 2 になり、地上に降りる。
- 魔物は地上にいるので、忍者が先に魔物を攻撃する。魔物の体力が 1 になる。
- 魔物が攻撃する。忍者の体力が 1 減る。
- 忍者が攻撃する。魔物は体力が 0 になり、倒れる。
入力例 3
4 3 5 4 1 6 2 0 4 5 1 3 2 0
出力例 3
25
Problem Statement
A ninja will fight against N monsters one by one in order. The attack power of the i-th monster is a_i, and its health is b_i. A monster is immediately defeated when its health becomes 0 or less.
Each monster is either on the ground or flying. If x_i = 0, the i-th monster is on the ground, and if x_i = 1, it is flying.
The ninja initially has M shurikens. Each shuriken can be used only once by throwing it.
The ninja and the i-th monster fight as follows:
- First, the ninja chooses zero or more shurikens from the ones he has and throws them at the monster. The monster's health decreases by the number of shurikens thrown, and if one or more shurikens are thrown at a flying monster, it lands on the ground.
- Then, the ninja and the monster take turns attacking each other. Each attack by the ninja decreases the monster's health by 1, and each attack by the monster decreases the ninja's health by a_i. Here, if the monster is on the ground, the ninja attacks first, and if it is flying, the monster attacks first.
Find the minimum possible difference between the ninja's initial health and his health after defeating all the monsters.
Assume that the ninja's health is sufficiently large.
Constraints
- 1 \leq N \leq 3 \times 10^5
- 0 \leq M \leq 10^{11}
- 1 \leq a_i, b_i \leq 3 \times 10^5
- x_i = 0 or x_i = 1.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M a_1 b_1 x_1 a_2 b_2 x_2 \vdots a_N b_N x_N
Output
Print the answer.
Sample Input 1
2 1 2 2 1 5 2 0
Sample Output 1
4
If the ninja fights as follows, his health will decrease by a total of 4, which is optimal:
- Do not throw any shurikens at the first monster.
- Since the monster is flying, it attacks the ninja first. The ninja's health decreases by 2.
- The ninja attacks. The monster's health becomes 1.
- The monster attacks. The ninja's health decreases by 2.
- The ninja attacks. The monster's health becomes 0, and it is defeated.
- Throw one shuriken at the second monster. The monster's health becomes 1.
- Since the monster is on the ground, the ninja attacks first. The monster's health becomes 0, and it is defeated.
Sample Input 2
1 2 1 4 1
Sample Output 2
1
If the ninja fights as follows, his health will decrease by a total of 1, which is optimal:
- Throw two shurikens at the first monster. The monster's health becomes 2, and it lands on the ground.
- Since the monster is on the ground, the ninja attacks first. The monster's health becomes 1.
- The monster attacks. The ninja's health decreases by 1.
- The ninja attacks. The monster's health becomes 0, and it is defeated.
Sample Input 3
4 3 5 4 1 6 2 0 4 5 1 3 2 0
Sample Output 3
25