题目描述

有 $N$ 座城镇，和城镇之间的 $M$ 条单向直达的巴士线路（没有中间停靠站）。城镇从 $1$ 到 $N$ 标号。一个旅行者在 $0$ 时刻位于 $1$ 号城镇，想要到达 $P$ 号城镇。他将乘坐巴士在 $T$ 时刻到达 $P$ 号城镇。如果他早到了，他必须等待。

对于任意一个巴士线路 $i$，我们知道其中的出发地城镇 $s_i$ 和目的地城镇 $t_i$。我们也同样知道 $i$ 的出发时间和到达时间，但仅仅是近似值：我们知道巴士离开出发地城镇 $s_i$ 在时间范围 $[a_i, b_i]$ 内，且到达目的地城镇 $t_i$ 在时间范围 $[c_i, d_i]$ 内（端点值包括在内）。

旅行者不喜欢等待，因此他要寻找一个旅行计划使得最大等待时间尽量小，同时保证绝对不会错过计划中的任何一辆巴士（意思是，每次他换乘巴士，他需要下车的巴士的最晚到达时间不会迟于他需要搭乘的下一辆巴士的最早出发时间）。

当计算等待时间时，我们必须假设最早可能到达的时间和最晚可能发车的时间。

编写一个程序，帮助旅行者寻找一个合适的计划。

输入格式

第一行包含整数 $N,M,P,T$，含义见题目描述。

接下来 $M$ 行描述了巴士线路。每行包含整数 $s_i, t_i, a_i, b_i, c_i, d_i$，其中 $s_i$ 和 $t_i$ 是巴士线路 $i$ 的出发地和目的地，$a_i, b_i, c_i, d_i$ 描述了出发和到达时间。

输出格式

仅一行，包含对于最合适的可能的旅行计划的最大的可能的总等待时间。如果不可能保证在 $T$ 时刻到达城镇 $P$，这一行应当包含 -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

提示

数据规模与约定

对于 $100\%$ 的数据，$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$。

说明

翻译自 BalticOI 2005 Day2 B Bus Trip。