问题陈述
忍者将对抗 N 怪兽按顺序一一对应。的攻击力 i- 第一个怪物是 a_i,其健康状况是 b_i。当怪物的生命值变为 0 或更少。
每个怪物要么在地面上,要么在飞行中。如果 x_i = 0, i- 第一个怪物在地面上,并且如果 x_i = 1,它正在飞。
忍者最初有 M 手里剑。每个手里剑只能通过投掷使用一次。
忍者和 i-第怪物战斗如下:
- 首先,忍者从他拥有的手里剑中选择零个或更多手里剑,并将它们扔向怪物。怪物的生命值会随着投掷手里剑的数量而减少,如果向飞行的怪物投掷一枚或多枚手里剑,它就会落在地面上。
- 然后,忍者和怪物轮流攻击对方。忍者的每次攻击都会使怪物的生命值减少 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 or 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,这是最佳的:
- 不要向第一个怪物扔任何手里剑。
- 由于怪物是飞行的,所以它首先攻击忍者。忍者的生命值减少 2.
- 忍者攻击。怪物的生命值变为 1.
- 怪物攻击。忍者的生命值减少 2.
- 忍者攻击。怪物的生命值变为 0,它被击败了。
- 向第二只怪物投掷一张手里剑。怪物的生命值变为 1.
- 由于怪物在地面上,所以忍者首先攻击。怪物的生命值变为 0,它被击败了。
示例输入 2
1 2 1 4 1
示例输出 2
1
如果忍者进行如下战斗,他的生命值将总共减少 1,这是最佳的:
- 向第一个怪物扔两个手里剑。怪物的生命值变为 2,然后它降落在地面上。
- 由于怪物在地面上,所以忍者首先攻击。怪物的生命值变为 1.
- 怪物攻击。忍者的生命值减少 1.
- 忍者攻击。怪物的生命值变为 0,它被击败了。
示例输入 3
4 3 5 4 1 6 2 0 4 5 1 3 2 0
示例输出 3
25