Problem Description

There are $N$ towns and $M$ one-way direct bus routes between the towns (with no intermediate stops). The towns are numbered from $1$ to $N$. A traveler is in town $1$ at time $0$ and wants to reach town $P$. He will arrive at town $P$ at time $T$ by taking buses. If he arrives earlier, he must wait.

For each bus route $i$, we know its starting town $s_i$ and destination town $t_i$. We also know its departure and arrival times, but only approximately: we know the bus leaves the starting town $s_i$ within the time interval $[a_i, b_i]$, and arrives at the destination town $t_i$ within the time interval $[c_i, d_i]$ (endpoints included).

The traveler dislikes waiting, so he wants to find a travel plan that minimizes the maximum waiting time, while also guaranteeing that he will never miss any bus in the plan (that is, each time he transfers, the latest possible arrival time of the bus he gets off is not later than the earliest possible departure time of the next bus he needs to take).

When computing waiting time, we must assume the earliest possible arrival time and the latest possible departure time.

Write a program to help the traveler find a suitable plan.

Input Format

The first line contains integers $N, M, P, T$, as described above.

The next $M$ lines describe the bus routes. Each line contains integers $s_i, t_i, a_i, b_i, c_i, d_i$, where $s_i$ and $t_i$ are the starting town and destination of route $i$, and $a_i, b_i, c_i, d_i$ describe the departure and arrival times.

Output Format

Output one line containing the maximum possible total waiting time for the best possible travel plan. If it is impossible to guarantee arrival at town $P$ at time $T$, this line should contain -1.

3 6 2 100
1 3 10 20 30 40
3 2 32 35 95 95
1 1 1 1 7 8
1 3 8 8 9 9
2 2 98 98 99 99
1 2 0 0 99 101

32

Hint

Constraints

For $100\%$ of the testdata, $1 \leq P \leq N \leq 5\times 10^4$, $1 \leq M \leq 10^5$, $0 \leq T \leq 10^9$, $1 \leq s_i, t_i \leq N$, $0 \leq a_i \leq b_i < c_i \leq d_i \leq 10^9$.

Notes

Translated from BalticOI 2005 Day2 B Bus Trip。

Translated by ChatGPT 5