文件输入输出提示

本题采用文件输入输出。提交代码时，请在 main 函数开头加入文件重定向，并从 link.in 读入、输出到 link.out。

freopen("link.in", "r", stdin);
freopen("link.out", "w", stdout);

题目描述

苗苗正在维护学校的数据中心。数据中心有 $n$ 个站点和 $m$ 条双向链路。第 $i$ 条链路连接站点 $u_i$ 和 $v_i$，它有两个属性：

• 稳定值 $q_i$；
• 传输耗时 $w_i$。

从 $s$ 到 $t$ 的一条传输路线可以经过若干条链路。

• 路线的总耗时：经过链路的耗时之和。
• 路线的稳定值：经过链路的稳定值中的最小值。

现在希望从站点 $s$ 向站点 $t$ 传输一份数据，要求总耗时不超过 $L$。请你在所有满足耗时限制的路线中，求出路线稳定值的最大可能值。

如果不存在总耗时不超过 $L$ 的路线，请输出 $-1$。

输入格式

从文件 link.in 中读入数据。

第一行输入五个整数 $n,m,s,t,L$。

接下来 $m$ 行，每行输入四个整数 $u_i,v_i,q_i,w_i$，表示一条双向链路。

输出格式

输出到文件 link.out 中。

输出一行一个整数，表示答案。

输入输出样例 #1

输入 #1

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

输出 #1

5

说明/提示

选择路线 $1\to 2\to 5$，总耗时为 $3+4=7$，不超过 $8$；路线稳定值为 $\min(5,5)=5$。

不存在总耗时不超过 $8$ 且路线稳定值大于 $5$ 的方案，因此答案为 $5$。

输入输出样例 #2

输入 #2

3 1 1 3 100
1 2 10 1

输出 #2

-1

数据范围与子任务

对于所有数据，满足：

• $1\le n\le 2\times 10^5$；
• $0\le m\le 2\times 10^5$；
• $1\le s,t\le n$；
• $s\ne t$；
• $1\le q_i\le 10^9$；
• $1\le w_i\le 10^9$；
• $0\le L\le 10^{18}$。

link_大样例.zip