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.
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$$$.
Print one integer: the minimum sum of the shift magnitudes.
2 101 1 12 7 1
5
3 82 0 35 3 29 0 8
0
3 71 2 23 0 18 6 1
3
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$$$.
| Название |
|---|


