Ленивец Сид решил научить зверей программированию. Из-за эпидемии новой коронавирусной инфекции, далеко не все звери могут посещать занятия очно. Поэтому, Сиду придется проводить некоторые занятия онлайн в LednikovyiZoom.
Очные занятия проводятся на лужайке, до которой ленивцу придется добираться из дома. Путь из дома до лужайки (или обратно) занимает t минут. Онлайн занятия можно проводить как из дома, так и используя трансляцию с лужайки. Во время занятия Сид не может перемещаться и должен на протяжении всего занятия находиться в одном месте: либо дома, либо на лужайке.
День Сида длится d минут. Обозначим начало дня моментом времени 0, тогда заканчивается день в момент времени d. В начале дня Сид просыпается дома, а в конце дня Сид ложится спать и тоже должен находиться дома. Сид очень любит свой дом и хочет провести там максимальное время в течении дня. Помогите ленивцу определить, сколько времени он сможет провести дома (онлайн занятия, проведенные из дома, считаются временем, проведенным дома).
В первой строке дано три целых числа n, d и t (1 ≤ n ≤ 10^5
, 1 ≤ d, t ≤ 10^18
) - количество занятий, длительность дня и время перехода между домом и лужайкой. В следующих n строках даны по три целых числа l[i]
, r[i]
и x[i]
- время начала i-го занятия, время окончания занятия и его тип (t ≤ l[i]
< r[i]
≤ d − t; x[i]
= 0 - очное занятие, x[i]
= 1 - онлайн). Гарантируется, что занятия не пересекаются по времени, однако время окончания одного может совпадать с временем начала другого.
Выведите максимальное время, которое Сид может провести дома в течении дня.