Sloth Sid decided to teach the animals how to program. Due to the epidemic of a new coronavirus infection, not all animals can attend classes in person. Therefore, Sid will have to conduct some classes online in LednikovyiZoom.

In-person classes are held on the lawn, to which the sloth will have to get from home. The walk from the house to the lawn (or back) takes t minutes. Online classes can be conducted both from home and using the broadcast from the lawn. During the session, Sid cannot move and must stay in one place throughout the session: either at home or on the lawn.

Sid's day lasts d minutes. Let's denote the beginning of the day by the time point 0, then the day ends at the time point d. At the beginning of the day, Sid wakes up at home, and at the end of the day, Sid goes to bed and must also be at home. Sid loves his house very much and wants to spend as much time there as possible during the day. Help the sloth figure out how much time he can spend at home (online activities done from home is a time spent at home).

Input

The first line contains three integers n, d and t (1 ≤ n ≤ 105, 1 ≤ * d, *t ≤ 1018) - the number of classes, the length of the day and the transition time between the house and the lawn. The next n lines contain three integers li, ri and xi - the start time of the i-th lesson, the end time of the lesson and its type (t ≤ li < ri ≤ d − t; xi = 0 - face-to-face lesson, xi = 1 - online). It is guaranteed that the classes do not overlap in time, however, the end time of one may coincide with the start time of another.

Output

Print the maximum time Sid can spend at home during the day.