小明运货

题号：NC221309
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小明是一个货车司机。
有一天，他要拉一些货，从地点 $x$ 到地点 $y$ ，然后空车返回。
已知城市里有很多公路。每条公路有限重 $p_i$ （即最大重量不能超过限重）。
现在给出城市的公路情况以及货车的重量 $w$ 。小明想保证他行驶的总路程不超过 $d$ ，他想知道自己能拉的货物最大重量是多少？

输入描述:

第一行 6 个正整数，，，，，，分别代表城市里的地点数量、公路条数、小明的起点、小明的终点、货车的重量、以及小明最大行驶的路程。
接下来的行，每行有四个正整数、、、，分别描述每条公路的起始地点、终止地点、限重以及这条公路的路程。
请注意，每条公路是双向的，两个地点之间也有可能不止一条公路。不保证和是连通的。

输出描述:

如果小明无论如何也无法完成运输，请输出 -1。如果小明能运的重量是0（即只能空车往返），也请输出-1。
否则输出一个正整数，代表能拉的货物重量的最大值。

示例1

输入

复制

3 3 1 3 10 11
1 2 14 3
3 2 12 3
1 3 11 4

输出

复制

说明

最大能运输的重量为2：
运输重量2的货物，加上货车的重量10，总重量为12。走第一条路和第二条路到3号地点，路程为3+3=6。请注意不能走3号公路，因为超出了11的限重。
然后返回时可以走3号公路了，因为空车重量为10，不超过3号公路。路程为4。
总路程为6+4=10，满足总路程不超过11。
可以证明，2即为最大的重量。因为假设运货重量为3，小明将不可能把货物运送到3号地点。

示例2

输入

复制

3 3 1 3 10 9
1 2 14 3
3 2 12 3
1 3 11 4

输出

复制

备注:

，