Minimizing Maximum Waiting Time in Bus Transfers

A traveler is located at town \(1\) at time \(0\) and wants to reach town \(P\) by bus such that he is (or will be) at town \(P\) at time \(T\). There are \(N\) towns (numbered \(1,2,\dots,N\)) and \(M\) directed bus routes between them. Each bus route \(i\) goes from town \(s_i\) to town \(t_i\) without intermediate stops. The departure time of bus route \(i\) is not fixed but is known to lie within the time interval \([a_i, b_i]\) (inclusive) and its arrival time lies within \([c_i, d_i]\) (inclusive).

When planning his journey, the traveler wishes to minimize the maximum waiting time that occurs either at the very beginning, during transfers, or at the destination. Waiting times are computed using optimistic and pessimistic values. Specifically:

• For the first bus taken from town \(1\), the waiting time is \(b_1 - 0\) (i.e. his waiting until the bus departs, using the bus's latest departure time \(b_1\)).
• For any transfer from bus \(i\) to bus \(j\), the traveler’s waiting time is \(b_j - c_i\), where \(c_i\) is the earliest possible arrival time of bus \(i\) and \(b_j\) is the latest possible departure time of the next bus \(j\).
• For the final leg, if the bus bringing him to town \(P\) has an earliest possible arrival time \(c_k\), he will have to wait \(T - c_k\) until time \(T\) (if \(c_k < T\)).

In addition, to guarantee that he does not miss any bus due to schedule uncertainties, the following safety condition must hold for every transfer: the latest possible arrival time of the bus he is alighting (i.e. \(d_i\) for bus \(i\)) must be no later than the earliest possible departure time of the bus he is boarding (i.e. \(a_j\) for bus \(j\)); formally, \(d_i \le a_j\).

The task is to choose a sequence of bus routes (a bus plan) starting from town \(1\) and ending at town \(P\) that satisfies the safety condition for every transfer and minimizes the maximum waiting time among all waiting periods (the initial wait, the transfer waits, and the final wait until \(T\)). If no such plan exists, output \(-1\).

Note: When computing waiting times, assume that for departure the traveler suffers the worst case (i.e. the bus departs at the latest possible time) and for arrival he gets the best case (i.e. the bus arrives at the earliest possible time).

inputFormat

The first line contains four integers \(N\), \(M\), \(P\) and \(T\) \((1 \le N \le \ldots,\; M \ge 1)\) where \(N\) is the number of towns, \(M\) is the number of bus routes, \(P\) is the destination town, and \(T\) is the desired arrival time at town \(P\). The next \(M\) lines each contain six integers:

\(s_i\; t_i\; a_i\; b_i\; c_i\; d_i\)

representing a bus route from town \(s_i\) to town \(t_i\), with departure time in \([a_i, b_i]\) and arrival time in \([c_i, d_i]\). All endpoints of the intervals are inclusive.

outputFormat

If a valid plan exists, output the minimum possible maximum waiting time (an integer). Otherwise, output \(-1\).

sample

3 3 3 10
1 2 1 2 3 4
2 3 5 6 7 8
1 3 0 3 8 9

3