题目内容

某厂区设有 $n$ 个卡口和 $m$ 条通道，卡口编号为 $1$ 至 $n$。

巡检人员需要从卡口 $s$ 出发，前往卡口 $t$（$s\ne t$），出发时刻为 $0$。

每个卡口 $i$ 都有一个允许进入的时间窗 $[L_i,R_i]$。若巡检人员在时刻 $x$ 到达卡口 $i$，则：

• 若 $x>R_i$，无法进入该卡口；
• 否则，实际进入时刻为 $\max(x,L_i)$。

巡检人员进入卡口后必须立即离开，不允许在卡口内额外等待。起点 $s$ 同样受时间窗限制，即巡检人员需要先进入卡口 $s$，再从该卡口出发。

每条通道由四个整数 $u,v,w,z$ 描述，表示该通道允许以下两种通行方式：

• 正向通行：从 $u$ 到 $v$，耗时 $w$；
• 反向通行：从 $v$ 到 $u$，耗时 $z$，消耗一次反向通行次数。

巡检人员最多可以反向通行 $K$ 次。

每条通道在一次巡检路径中最多使用一次，无论正向还是反向。输入中的每条通道均视为独立通道，即使其连接的卡口相同。

请计算巡检人员最早进入卡口 $t$ 的时刻。如果不存在满足要求的巡检路径，输出 $-1$。

输入描述

第一行包含三个整数 $n$、$m$、$K$，分别表示卡口数量、通道数量和允许的最大反向通行次数。

第二行包含两个整数 $s$、$t$，表示起点和终点。

接下来 $n$ 行，每行包含两个整数 $L_i$、$R_i$，表示卡口 $i$ 的进入时间窗。

接下来 $m$ 行，每行包含四个整数 $u$、$v$、$w$、$z$，表示一条通道：正向从 $u$ 到 $v$ 耗时 $w$，反向从 $v$ 到 $u$ 耗时 $z$。

约束

$2 \le n \le 10^5$

$0 \le m \le 2\times 10^5$

$0 \le K \le 10$

$1 \le s,t \le n$，且 $s\ne t$

$0 \le L_i \le R_i \le 10^9$

$1 \le u,v \le n$，且 $u\ne v$

$1 \le w,z \le 10^9$

保证存在合法路径时，答案不超过 $10^{18}$。

输出描述

输出一个整数，表示最早进入卡口 $t$ 的时刻。如果无法到达，输出 $-1$。

样例1

输入

4 5 1
1 4
0 50
10 12
0 4
12 40
1 2 4 4
2 3 1 1
3 4 10 10
4 2 100 3
1 4 25 25

输出

13

说明

选择路径 $1\to 2\to 4$。

巡检人员在时刻 $0$ 从卡口 $1$ 出发，正向经过通道 $1\to 2$，耗时 $4$，在时刻 $4$ 到达卡口 $2$。

由于卡口 $2$ 的进入时间窗为 $[10,12]$，巡检人员需要等待至时刻 $10$ 才能进入并离开。

随后反向使用通道 $4\to 2$，从卡口 $2$ 前往卡口 $4$，耗时 $3$，在时刻 $13$ 进入终点。

该路径使用了一次反向通行，满足限制，最早进入终点的时刻为 $13$。

样例2

输入

3 4 1
1 3
0 100
0 100
0 100
2 1 100 1
1 2 6 100
3 2 100 1
2 3 10 100

输出

7

说明

选择路径 $1\to 2\to 3$。

首先正向使用通道 $1\to 2$，耗时 $6$，在时刻 $6$ 进入卡口 $2$。

随后反向使用通道 $3\to 2$，耗时 $1$，在时刻 $7$ 进入卡口 $3$。

虽然可以通过连续两次反向通行在时刻 $2$ 到达终点，但反向次数超过 $K=1$，因此不合法。

故最早进入终点的时刻为 $7$。