CF1430F.Realistic Gameplay

Recently you've discovered a new shooter. They say it has realistic game mechanics.

Your character has a gun with magazine size equal to $k$ and should exterminate $n$ waves of monsters. The $i$-th wave consists of $a_i$ monsters and happens from the $l_i$-th moment of time up to the $r_i$-th moments of time. All $a_i$ monsters spawn at moment $l_i$ and you have to exterminate all of them before the moment $r_i$ ends (you can kill monsters right at moment $r_i$). For every two consecutive waves, the second wave starts not earlier than the first wave ends (though the second wave can start at the same moment when the first wave ends) — formally, the condition $r_i \le l_{i + 1}$ holds. Take a look at the notes for the examples to understand the process better.

You are confident in yours and your character's skills so you can assume that aiming and shooting are instant and you need exactly one bullet to kill one monster. But reloading takes exactly $1$ unit of time.

One of the realistic mechanics is a mechanic of reloading: when you reload you throw away the old magazine with all remaining bullets in it. That's why constant reloads may cost you excessive amounts of spent bullets.

You've taken a liking to this mechanic so now you are wondering: what is the minimum possible number of bullets you need to spend (both used and thrown) to exterminate all waves.

Note that you don't throw the remaining bullets away after eradicating all monsters, and you start with a full magazine.

最近，你发现了一款新的射击游戏。据说它拥有逼真的游戏机制。

你的角色拥有一把弹匣容量为 $k$ 的枪，需要消灭 $n$ 波怪物。第 $i$ 波怪物包含 $a_i$ 只怪物，出现的时间段为从时刻 $l_i$ 到时刻 $r_i$（含端点）。所有 $a_i$ 只怪物均在时刻 $l_i$ 同时生成，而你必须在时刻 $r_i$ 结束前将它们全部消灭（你可以在时刻 $r_i$ 精确地击杀怪物）。对于任意两波连续的怪物，后一波的开始时间不早于前一波的结束时间（但后一波可以恰好在前一波结束的同一时刻开始）——形式化地说，满足条件 $r_i \le l_{i + 1}$。请参阅示例的注释以更清晰地理解整个过程。

你对自己的操作和角色能力充满信心，因此可假设瞄准与射击均为瞬时动作，且击杀一只怪物恰好需要一发子弹。但装填（reload）恰好耗时 $1$ 单位时间。

其中一项逼真机制是装填机制：当你装填时，会丢弃当前弹匣中所有剩余的子弹。正因如此，频繁装填可能导致大量子弹被无谓浪费。

你十分喜爱这一机制，因此现在你想知道：为消灭所有怪物波次，所需消耗的子弹总数（包括实际击中怪物所用的子弹，以及装填时被丢弃的子弹）的最小可能值是多少？

注意：在消灭全部怪物后，你无需丢弃弹匣中剩余的子弹；初始时你的弹匣是满的。

The first line contains two integers $n$ and $k$ ($1 \le n \le 2000$; $1 \le k \le 10^9$) — the number of waves and magazine size.

The next $n$ lines contain descriptions of waves. The $i$-th line contains three integers $l_i$, $r_i$ and $a_i$ ($1 \le l_i \le r_i \le 10^9$; $1 \le a_i \le 10^9$) — the period of time when the $i$-th wave happens and the number of monsters in it.

It's guaranteed that waves don't overlap (but may touch) and are given in the order they occur, i. e. $r_i \le l_{i + 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$ 波发生的时间区间以及该波中的怪物数量。

保证各波次互不重叠（但可以相接），且按发生顺序给出，即满足 $r_i \le l_{i + 1}$。

If there is no way to clear all waves, print $-1$. Otherwise, print the minimum possible number of bullets you need to spend (both used and thrown) to clear all waves.

如果无法清除所有波次，则输出 $-1$。否则，输出清除所有波次所需的最少子弹数量（包括已使用和已丢弃的子弹）。

In the first example:

• At the moment $2$, the first wave occurs and $6$ monsters spawn. You kill $3$ monsters and start reloading.
• At the moment $3$, the second wave occurs and $3$ more monsters spawn. You kill remaining $3$ monsters from the first wave and start reloading.
• At the moment $4$, you kill remaining $3$ monsters from the second wave.

In total, you'll spend $9$ bullets.

In the second example:

• At moment $3$, the first wave occurs and $11$ monsters spawn. You kill $5$ monsters and start reloading.
• At moment $4$, you kill $5$ more monsters and start reloading.
• At moment $5$, you kill the last monster and start reloading throwing away old magazine with $4$ bullets.
• At moment $10$, the second wave occurs and $15$ monsters spawn. You kill $5$ monsters and start reloading.
• At moment $11$, you kill $5$ more monsters and start reloading.
• At moment $12$, you kill last $5$ monsters.

In total, you'll spend $30$ bullets.

在第一个例子中：

• 在时刻 $2$，第一波怪物来袭，生成 $6$ 只怪物。你击杀其中 $3$ 只，并开始换弹。
• 在时刻 $3$，第二波怪物来袭，额外生成 $3$ 只怪物。你击杀第一波剩余的 $3$ 只怪物，并开始换弹。
• 在时刻 $4$，你击杀第二波剩余的 $3$ 只怪物。

总共，你将消耗 $9$ 发子弹。

在第二个例子中：

• 在时刻 $3$，第一波怪物来袭，生成 $11$ 只怪物。你击杀其中 $5$ 只，并开始换弹。
• 在时刻 $4$，你再击杀 $5$ 只怪物，并开始换弹。
• 在时刻 $5$，你击杀最后 $1$ 只怪物，并开始换弹，此时丢弃装有 $4$ 发子弹的旧弹匣。
• 在时刻 $10$，第二波怪物来袭，生成 $15$ 只怪物。你击杀其中 $5$ 只，并开始换弹。
• 在时刻 $11$，你再击杀 $5$ 只怪物，并开始换弹。
• 在时刻 $12$，你击杀最后 $5$ 只怪物。

总共，你将消耗 $30$ 发子弹。