H. Hacking the Traffic Lights
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A student team in Limassol is tired of being late because the traffic lights on their way to the university are poorly synchronized.

There are $$$n$$$ traffic lights along their path. The car starts at an integer time $$$x\ge 0$$$ and reaches the $$$i$$$-th light exactly $$$d_i$$$ seconds later, without stopping.

All lights have the same integer period $$$c$$$. Originally, light $$$i$$$ is green at an integer time $$$t$$$ if $$$(t-s_i)\bmod c$$$ belongs to $$$\{0,1,\ldots,g_i-1\}$$$. Remainders are taken between $$$0$$$ and $$$c-1$$$: the green interval may wrap around the period, and $$$g_i=c$$$ means the light is always green.

The team has found a backdoor in the road department's server. They can shift each light's phase independently in either direction. Choose a nonnegative integer shift magnitude $$$\delta_i\in\{0,1,\ldots,c-1\}$$$ for each light, and replace $$$s_i$$$ with either $$$(s_i+\delta_i)\bmod c$$$ or $$$(s_i-\delta_i)\bmod c$$$.

Choose the starting time and phase shifts so that the car passes every light on green. Minimize $$$\sum_{i=1}^{n}\delta_i$$$, the sum of the shift magnitudes.

Input

The first line contains two integers $$$n$$$ and $$$c$$$ ($$$1\le n\le 200\,000$$$, $$$1\le c\le 10^9$$$), the number of traffic lights and their common period.

Each of the next $$$n$$$ lines contains three integers $$$d_i$$$, $$$s_i$$$, and $$$g_i$$$ ($$$1\le d_i\le 10^9$$$, $$$0\le s_i \lt c$$$, $$$1\le g_i\le c$$$), describing the $$$i$$$-th light. The travel times satisfy $$$d_1 \lt d_2 \lt \cdots \lt d_n$$$.

Output

Print one integer: the minimum sum of the shift magnitudes.

Examples
Input
2 10
1 1 1
2 7 1
Output
5
Input
3 8
2 0 3
5 3 2
9 0 8
Output
0
Input
3 7
1 2 2
3 0 1
8 6 1
Output
3
Note

In the first example, start at $$$x=0$$$ and shift the second light by $$$5$$$ seconds. Both lights are then green at the arrival times, $$$1$$$ and $$$2$$$. The total cost is $$$5$$$.

In the second example, start at $$$x=6$$$. The arrival remainders are $$$0$$$, $$$3$$$, and $$$7$$$, so no shifts are needed.

In the third example, start at $$$x=4$$$, shift the first light by $$$2$$$ seconds and the third by $$$-1$$$ second, and leave the second light unchanged. The total cost is $$$3$$$.