该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

未来世界，一片区域遭受了严重的辐射污染。这片区域由 N 个据点（编号 1 到 N）和 M 条双向通道组成。

每条通道都有两个属性：

• 辐射强度 Ri：通过这条通道时，人体暴露在的辐射强度。
• 通行时间 Ti：通过这条通道所花费的时间。

救援队需要从起点 S 运送物资到终点 T。 物资对辐射非常敏感，虽然防护服可以抵御辐射，但防护服有一个“辐射承受上限” X。

如果一条通道的辐射强度 Ri 超过了 X，救援队就绝对不能走这条路。 如果 Ri ≤ X，则可以安全通过（对物资无损耗）。

同时，由于伤员情况危急，救援队必须在总时间限制 K 内到达终点。

任务

请你帮助救援队计算，为了在不超过总时间 K 的前提下到达终点， 防护服的最低辐射承受上限 X 应该是多少？

如果无论如何都无法在时间 K 内到达终点，请输出 -1。

输入格式

• 第一行包含五个整数 N, M, S, T, K 分别表示据点数、通道数、起点、终点、总时间限制。
• 接下来 M 行，每行包含四个整数 u, v, r, t 表示据点 u 和 v 之间有一条双向通道， 辐射强度为 r，通行时间为 t。

输出格式

• 输出一个整数，表示满足条件的最小辐射承受上限 X。 如果不连通或无法在限制时间内到达，输出 -1。

数据范围

• 1 ≤ N ≤ 50000
• 1 ≤ M ≤ 100000
• 1 ≤ S, T ≤ N
• 1 ≤ K ≤ 10^9
• 1 ≤ r, t ≤ 100000

样例

样例输入（radiation.in）

4 5 1 4 15
1 2 2 5
1 3 5 4
2 4 8 6
3 4 3 15
2 3 2 2

样例输出（radiation.out）

8