Work from home#11264
Sloth Sid decided to teach the animals programming. Due to the outbreak of a new coronavirus infection, not all animals can attend classes in person. Therefore, Sid has to conduct some of the classes online using LednikovyiZoom.
In-person classes take place on a meadow, which Sid must travel to from his home. The trip from home to the meadow (and back) takes minutes. Online classes can be conducted either from home or from the meadow. During any class, Sid cannot move and must remain in the same place for its entire duration: either at home or on the meadow.
Sid's day lasts minutes. The moment marks the beginning of the day, and the moment marks its end. At the beginning of the day, Sid wakes up at home; at the end of the day, he goes to sleep and must also be at home. Sid loves his home very much and wants to spend as much time there as possible. Help him determine how much time he can spend at home (online classes conducted from home count as time spent at home).
The first line contains three integers and t~(1 \le n \le 10^5, 1 \le d, t \le 10^{18}) — the number of classes, the duration of the day, and the travel time between home and the meadow.
Each of the next lines contains three integers l_i, r_i~(t \le l_i < r_i \le d - t) and x_i~(x_i = 0 for an in-person class, x_i = 1 for an online class) — the starting time of the -th class, the ending time, and its type.
It is guaranteed that the classes do not overlap in time, although the ending time of one class may coincide with the starting time of another.
Output the maximum amount of time Sid can spend at home during the day.
Example 1
Example 2