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 翻译