Bus Trip#3017
There are towns and one-way direct bus routes between them (no intermediate stops). The towns are numbered from to . A traveler located in town at time must arrive in town . He will be picked up from the bus station in town exactly at time . If he arrives earlier, he will have to wait.
For each bus route , the source and destination towns s_i and t_i are given. We also know the departure and arrival times, but only approximately: the bus departs from s_i within the range [a_i, b_i] and arrives at t_i within the range [c_i, d_i] (endpoints included in both cases).
The traveler does not like waiting and therefore is looking for a travel plan that minimizes the maximal possible waiting time, while still guaranteeing that he will not miss connecting buses (that is, every time he changes buses, the latest possible arrival of the incoming bus must not be later than the earliest possible departure of the outgoing bus).
When counting waiting time, we have to consider the earliest possible arrival time and the latest possible departure time.
Write a program to help the traveler find a suitable plan.
The first line contains the integers (1 \leq N \leq 50000), (1 \leq M \leq 100000), (1 \leq P \leq N), and (0 \leq T \leq 1000000000).
The next lines describe the bus routes. Each line contains the integers s_i, t_i, a_i, b_i, c_i, d_i, where s_i and t_i are the source and destination towns of the bus route , and a_i, b_i, c_i, d_i describe the departure and arrival times as explained above (1 \leq s_i \leq N, 1 \leq t_i \leq N, 0 \leq a_i \leq b_i < c_i \leq d_i \leq 1000000000).
The only line of the output file should contain the maximal possible total waiting time for the most suitable travel plan. If it is not possible to guarantee arrival in town by time , the line should contain .
Example 1