CF1430F Realistic Gameplay

最近你发现了一款新的射击游戏。据说它拥有非常真实的游戏机制。 你的角色拥有一把弹匣容量为 $k$ 的枪，需要消灭 $n$ 波怪物。第 $i$ 波怪物共有 $a_i$ 只，出现在时间区间 $[l_i, r_i]$。所有 $a_i$ 只怪物会在 $l_i$ 时刻同时出现，你必须在 $r_i$ 时刻结束前消灭所有怪物（你可以在 $r_i$ 时刻正好消灭怪物）。对于任意两波相邻的怪物，后一波的开始时间不会早于前一波的结束时间（即后一波可以在前一波结束的同一时刻开始），形式化地说，满足 $r_i \le l_{i+1}$。你可以参考样例说明来更好地理解流程。 你对自己和角色的射击技术非常自信，可以假设瞄准和射击都是瞬间完成的，并且每只怪物只需一发子弹即可消灭。但每次换弹需要恰好 $1$ 单位时间。 其中一个真实的机制就是换弹：每次换弹时，你会丢弃当前弹匣中所有剩余的子弹。因此频繁换弹可能会导致大量子弹浪费。 你很喜欢这个机制，所以现在你想知道：消灭所有怪物波所需消耗（包括用掉和丢弃的）子弹的最小数量是多少。 注意，消灭所有怪物后你不需要再丢弃剩余子弹，并且你一开始拥有满弹匣。

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2000$，$1 \le k \le 10^9$），分别表示怪物波的数量和弹匣容量。 接下来的 $n$ 行，每行包含三个整数 $l_i$、$r_i$ 和 $a_i$（$1 \le l_i \le r_i \le 10^9$，$1 \le a_i \le 10^9$），分别表示第 $i$ 波怪物出现的时间区间和怪物数量。 保证所有怪物波不会重叠（但可以相接），并且按出现顺序给出，即 $r_i \le l_{i+1}$。

如果无法消灭所有怪物，输出 $-1$。否则，输出消灭所有怪物所需消耗（包括用掉和丢弃的）子弹的最小数量。

在第一个样例中： - 在时刻 $2$，第一波怪物出现，共 $6$ 只。你消灭 $3$ 只怪物，然后开始换弹。 - 在时刻 $3$，第二波怪物出现，又出现 $3$ 只怪物。你消灭第一波剩下的 $3$ 只怪物，然后开始换弹。 - 在时刻 $4$，你消灭第二波剩下的 $3$ 只怪物。 总共消耗了 $9$ 发子弹。 在第二个样例中： - 在时刻 $3$，第一波怪物出现，共 $11$ 只。你消灭 $5$ 只怪物，然后开始换弹。 - 在时刻 $4$，你再消灭 $5$ 只怪物，然后开始换弹。 - 在时刻 $5$，你消灭最后一只怪物，然后换弹，丢弃弹匣中剩余的 $4$ 发子弹。 - 在时刻 $10$，第二波怪物出现，共 $15$ 只。你消灭 $5$ 只怪物，然后开始换弹。 - 在时刻 $11$，你再消灭 $5$ 只怪物，然后开始换弹。 - 在时刻 $12$，你消灭最后 $5$ 只怪物。 总共消耗了 $30$ 发子弹。 由 ChatGPT 4.1 翻译