Робота з дому
Лінивець Сід вирішив навчити звірів програмуванню. Через епідемію нової коронавірусної інфекції, не всі звірі можуть відвідувати заняття очно. Тому Сіду доведеться проводити деякі заняття онлайн у 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 - онлайн). Гарантується, що заняття не перетинаються за часом, однак час закінчення одного може збігатися з часом початку іншого.
Вихідні дані
Виведіть максимальний час, який Сід може провести вдома протягом дня.