Realistic Gameplay
Contest: Educational Codeforces Round 96 (Rated for Div. 2)
Difficulty rating: 2600
Tags: dp, greedy

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.

Input format:
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}$$$.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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 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.

Example input:
2 3
2 3 6
3 4 3

Example output:
9

Example input:
2 5
3 7 11
10 12 15

Example output:
30

Editorial:
Note some observations: if we meet a new wave and start shooting it's optimal to shoot monsters in the wave using full magazines while we can and there are no reasons to take breaks between shooting monsters from one wave. That's why we can track only moments when waves start and the number of remaining bullets in magazine we have at these moments.
Moreover, since the next wave starts not earlier than the previous ends, we can think that when we start dealing with one wave we've already dealt with the previous one. Also, instead of keeping track of the remaining bullets, let's just look only at such indices of waves when we reloaded and threw remaining bullets before reaching them.
So, we can write the next dp: $$$d[i]$$$ is the minimum number of bullets we spend dealing with the first $$$i$$$ waves and now we standing at the moment $$$l_i$$$ with full magazine. Obviously, $$$dp[0] = 0$$$.
Now, with fixed $$$i$$$ we can iterate over the index $$$j$$$ of a wave before which we'll reload throwing away remaining bullets. And for waves $$$[i, j)$$$ we need to check that we are able to exterminate all these waves without throwing away any bullets. We can check it with several formulas.
If it's possible for segment $$$[i, j)$$$ then the possibility for the segment $$$[i, j + 1)$$$ is just checking that we can exterminate the $$$j$$$-th wave having $$$rem \ge 0$$$ bullets in the start in no more than $$$r_j - l_j$$$ reloads plus checking that we have at least one unit before $$$l_{j + 1}$$$ for a reload.
As a result, the time complexity of the solution is $$$O(n^2)$$$.