← 返回题目列表

AtCoder · past202306_j

J. 忍者

中文机器翻译题面 查看原题

问题陈述

忍者将对抗 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