[Baltic2005]Trip

有 $N$ 座城镇和 $M$ 条单向巴士路线，每条路线中途均不停车。城镇编号为 $1$ 到 $N$。

一名旅行者在时刻 $0$ 位于城镇 $1$，希望在时刻 $T$ 位于城镇 $P$。如果提前到达，他必须在城镇中等待。

对于第 $i$ 条巴士路线，已知其起点城镇 $s_i$ 和终点城镇 $t_i$。巴士的出发和到达时间只能确定在一定范围内：它会在闭区间 $[a_i,b_i]$ 内离开城镇 $s_i$，并在闭区间 $[c_i,d_i]$ 内到达城镇 $t_i$。

旅行者不喜欢等待，因此希望选择一个旅行方案，使总等待时间在最坏情况下尽可能短。同时，该方案必须保证他绝对不会错过任何一辆计划乘坐的巴士。也就是说，每次换乘时，前一辆巴士的最晚到达时间不能晚于后一辆巴士的最早出发时间。

计算最坏情况下的等待时间时，应假设旅行者乘坐的巴士尽早到达，而下一辆巴士尽晚出发。旅行开始前在城镇 $1$ 的等待时间，以及抵达城镇 $P$ 后直到时刻 $T$ 的等待时间，也计入总等待时间。

请计算所有可行旅行方案中，最坏情况下总等待时间的最小值。

输入格式

第一行包含四个整数 $N$、$M$、$P$ 和 $T$，分别表示城镇数量、巴士路线数量、目的地城镇编号和目标时刻。

接下来 $M$ 行，每行包含六个整数 $s_i$、$t_i$、$a_i$、$b_i$、$c_i$、$d_i$，描述一条巴士路线。其中，$s_i$ 和 $t_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

样例解释

该旅行方案在最坏情况下的过程如下：

• 时刻 $0$ 至 $1$：在城镇 $1$ 等待；
• 时刻 $1$ 至 $7$：乘坐第 $3$ 条路线，从城镇 $1$ 到城镇 $1$；
• 时刻 $7$ 至 $8$：在城镇 $1$ 等待；
• 时刻 $8$ 至 $9$：乘坐第 $4$ 条路线，从城镇 $1$ 到城镇 $3$；
• 时刻 $9$ 至 $35$：在城镇 $3$ 等待；
• 时刻 $35$ 至 $95$：乘坐第 $2$ 条路线，从城镇 $3$ 到城镇 $2$；
• 时刻 $95$ 至 $98$：在城镇 $2$ 等待；
• 时刻 $98$ 至 $99$：乘坐第 $5$ 条路线，从城镇 $2$ 到城镇 $2$；
• 时刻 $99$ 至 $100$：在城镇 $2$ 等待。

总等待时间为：

$$1+1+26+3+1=32。$$

数据范围

• $1\le N\le 5\times 10^4$；
• $1\le M\le 10^5$；
• $1\le P\le N$；
• $0\le T\le 10^9$；
• $1\le s_i\le N$，$1\le t_i\le N$；
• $0\le a_i\le b_i<c_i\le d_i\le 10^9$。

来源与许可

本题为 Baltic OI 2005 试题「Trip」，题面与测试数据整理自 BZOJ 1395。

样例 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