最近你发现了一个新的射手。他们说它具有现实的游戏机制。
你的角色有一把弹匣大小为 $$$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$$$怪物。