Робота з дому#11264

Робота з дому

1 секунда

128 мегабайтів

Складна

Лінивець Сід вирішив навчити звірів програмуванню. Через епідемію нової коронавірусної інфекції далеко не всі звірі можуть відвідувати заняття очно. Тому Сіду доводиться проводити частину занять онлайн в LednikovyiZoom.

Очні заняття проходять на галявині, до якої Сідові потрібно добиратися з дому. Перехід від дому до галявини (і назад) займає $t$ хвилин. Онлайн-заняття можна проводити як з дому, так і з галявини. Під час заняття Сід не може переміщуватися і повинен знаходитися в одному місці протягом всього заняття: або вдома, або на галявині.

День Сіда триває $d$ хвилин. Початком дня вважається момент часу $0$ , кінцем — момент часу $d$ . На початку дня Сід прокидається вдома, а в кінці дня лягає спати і також повинен знаходитися вдома. Сід дуже любить свій дім і хоче провести в ньому якомога більше часу. Допоможіть йому визначити, скільки часу він зможе провести вдома (онлайн-заняття, проведені з дому, вважаються часом, проведеним вдома).

Вхідні дані

У першому рядку дано три цілі числа $n, d$ і $t (1 \leq n \leq 1 0^{5}, 1 \leq d, t \leq 1 0^{18})$ t~(1 \le n \le 10^5, 1 \le d, t \le 10^{18}) — кількість занять, тривалість дня і час переходу між домом та галявиною.

У наступних $n$ рядках задано по три цілі числа $l_{i}, r_{i} (t \leq l_{i} < r_{i} \leq d - t)$ l_i, r_i~(t \le l_i < r_i \le d - t) і $x_{i} (x_{i} = 0$ x_i~(x_i = 0 — очне заняття, $x_{i} = 1$ x_i = 1 — онлайн) — час початку $i$ -го заняття, час закінчення заняття і його тип.

Гарантується, що заняття не перетинаються за часом, проте закінчення одного може збігатися з початком іншого.

Вихідні дані

Виведіть максимальний час, який Сід може провести вдома протягом дня.

Приклади

Приклад 1

Приклад 2