AT_past202306_j.忍者

一名忍者将依次与 $N$ 个怪物逐一战斗。第 $i$ 个怪物的攻击力为 $a_i$，生命值为 $b_i$。当怪物的生命值降至 $0$ 或以下时，会立刻被击败。
每个怪物要么在地面上，要么在空中。如果 $x_i=0$，则第 $i$ 个怪物在地面上；如果 $x_i=1$，则在空中。

忍者一开始有 $M$ 个手里剑。每个手里剑只能使用一次，通过投掷使用。
忍者与第 $i$ 个怪物的战斗过程如下：

• 首先，忍者可以选择用手里的若干枚手里剑投掷怪物（可为零）。每投掷一枚，怪物的生命值减少 $1$。若对空中的怪物投掷至少一枚手里剑，则该怪物会落到地上。
• 然后，忍者与怪物轮流攻击对方。每次忍者攻击都会使怪物的生命值减少 $1$；每次怪物攻击都会使忍者的生命值减少 $a_i$。这里，如果怪物在地面上，则忍者先攻击，否则怪物先攻击。

请你求出，击败所有怪物后，忍者初始生命值与剩余生命值之间的最小可能差值。
已知忍者的生命值足够大。

输入由标准输入给出，格式如下：

$N$ $M$
$a_1$ $b_1$ $x_1$
$a_2$ $b_2$ $x_2$
$\vdots$
$a_N$ $b_N$ $x_N$

输出答案。

样例解释 1

若忍者如下操作，总共生命值减少了 $4$，且这是最优的：

• 第一个怪物，不投掷手里剑。
  • 由于怪物在空中，怪物先攻击，忍者生命减 $2$。
  • 忍者攻击，怪物生命变为 $1$。
  • 怪物攻击，忍者生命再减 $2$。
  • 忍者攻击，怪物生命变为 $0$，战斗结束。
• 第二个怪物，投掷一枚手里剑，怪物生命变为 $1$。
  • 由于怪物在地面，忍者先攻击，怪物生命变 $0$，战斗结束。

样例解释 2

若忍者如下操作，总共生命值减少了 $1$，且这是最优的：

• 第一个怪物，投掷两枚手里剑，怪物生命变为 $2$，并落地。
  • 由于怪物在地面，忍者先攻击，怪物剩 $1$。
  • 怪物攻击，忍者生命减 $1$。
  • 忍者攻击，怪物生命变为 $0$，战斗结束。

数据范围

• $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$
• 所有输入均为整数。

由 ChatGPT 5 翻译