Ленивец Сид решил научить зверей программированию. Из-за эпидемии новой коронавирусной инфекции, далеко не все звери могут посещать занятия очно. Поэтому, Сиду придется проводить некоторые занятия онлайн в LednikovyiZoom.

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

День Сида длится d минут. Обозначим начало дня моментом времени 0, тогда заканчивается день в момент времени d. В начале дня Сид просыпается дома, а в конце дня Сид ложится спать и тоже должен находиться дома. Сид очень любит свой дом и хочет провести там максимальное время в течении дня. Помогите ленивцу определить, сколько времени он сможет провести дома (онлайн занятия, проведенные из дома, считаются временем, проведенным дома).

Входные данные

В первой строке дано три целых числа n, d и t (1 ≤ n ≤ 105, 1 ≤ d, t ≤ 1018) - количество занятий, длительность дня и время перехода между домом и лужайкой. В следующих n строках даны по три целых числа li, ri и xi - время начала i-го занятия, время окончания занятия и его тип (t ≤ li < ri ≤ d − t; xi = 0 - очное занятие, xi = 1 - онлайн). Гарантируется, что занятия не пересекаются по времени, однако время окончания одного может совпадать с временем начала другого.

Выходные данные

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