← 返回题目列表

Codeforces · 1430/F

F. 逼真的游戏

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

最近你发现了一个新的射手。他们说它具有现实的游戏机制。

你的角色有一把弹匣大小为 $$$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$$$ 行包含波浪的描述。第 $$$i$$$ 行包含三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$a_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$; $$$1 \le a_i \le 10^9$$$) – 第 $$$i$$$ 波发生的时间段和怪物数量它。

保证波不会重叠(但可能接触)并且按照它们发生的顺序给出,即。 e. $$$r_i \le l_{i + 1}$$$。

输出

如果无法清除所有波浪,则打印$$$-1$$$。否则,打印清除所有波浪所需花费的最小子弹数(使用过的和投掷的子弹)。

示例

输入 #1

2 3
2 3 6
3 4 3

输出 #1

9

输入 #2

2 5
3 7 11
10 12 15

输出 #2

30

输入 #3

5 42
42 42 42
42 43 42
43 44 42
44 45 42
45 45 1

输出 #3

-1

输入#4

1 10
100 111 1

输出#4

1

注意

在第一个示例中:

- 此时$$$2$$$,第一波发生并且$$$6$$$怪物产卵。你杀死了 $$$3$$$ 怪物并开始重新加载。
- 此时$$$3$$$,第二波发生,并且产生了$$$3$$$更多怪物。你杀死第一波剩余的 $$$3$$$ 怪物并开始重新加载。
- 此时$$$4$$$,你杀死了第二波剩余的$$$3$$$怪物。

在第二个示例中:

- 在 $$$3$$$ 时刻,第一波发生并产生 $$$11$$$ 怪物。你杀死 $$$5$$$ 怪物并开始重新加载。
- 在$$$4$$$时刻,你杀死了$$$5$$$以上的怪物并开始重新加载。
- 在 $$$5$$$ 时刻,你杀死了最后一个怪物并开始重新装弹并扔掉装有 $$$4$$$ 子弹的旧弹匣。
- 在$$$10$$$时刻,第二波发生并且$$$15$$$怪物产卵。你杀死 $$$5$$$ 怪物并开始重新加载。
- 在$$$11$$$时刻,你又杀死了$$$5$$$怪物并开始重新加载。
- 在$$$12$$$时刻,你杀死了最后$$$5$$$怪物。