C. 旅游路线

T 城是一个旅游城市，具有 个景点和 条道路，所有景点编号为 。每条道路连接这 个景区中的某两个景区，道路是单向通行的。每条道路都有一个长度。

为了方便旅游，每个景点都有一个加油站。第 个景点的加油站的费用为 ，加油量为 。若汽车在第 个景点加油，则需要花费 元钱，之后车的油量将被加至油量上限与 中的较小值。不过如果加油前汽车油量已经不小于 ，则不能在该景点加油。

小 C 准备来到 T 城旅游。他的汽车油量上限为 。旅游开始时，汽车的油量为 。在旅游过程中：

1、当汽车油量大于 时，汽车可以沿从当前景区出发的任意一条道路到达另一个景点（不能只走道路的一部分），汽车油量将减少 ；

2、当汽车在景点 且当前油量小于 时，汽车可以在当前景点加油，加油需花费 元钱，这样汽车油量将变为 。

一次旅游的总花费等于每次加油的花费之和，旅游的总路程等于每次经过道路的长度之和。注意多次在同一景点加油，费用也要计算多次，同样地，多次经过同一条道路，路程也要计算多次。

小 C 计划旅游 次，每次旅游前，小 C 都指定了该次旅游的起点和目标路程。由于行程不同，每次出发前带的钱也不同。为了省钱，小 C 需要在旅游前先规划好旅游路线（包括旅游的路径和加油的方案），使得从起点出发，按照该旅游路线旅游结束后总路程不小于目标路程，且剩下的钱尽可能多。请你规划最优旅游路线，计算这 次旅游每次结束后最多可以剩下多少钱。

输入第一行包含四个正整数 ，，，，每两个整数之间用一个空格隔开，分别表示景点数、道路数、汽车油量上限和旅行次数。

接下来 行，每行包含两个正整数 ，，每两个整数之间用一个空格隔开，按编号顺序依次表示编号为 的景点的费用和油量。

接下来 行，每行包含三个正整数 ，，，每两个整数之间用一个空格隔开，表示一条从编号为 的景点到编号为 的景点的道路，道路的长度为 。保证 ，但从一个景点到另一个景点可能有多条道路。

最后 行，每行包含三个正整数 ，，，描述一次旅游计划，旅游的起点为编号为 的景点，出发时带了 元钱，目标路程为 。

输出 行，每行一个整数，第 行的整数表示第 次旅游结束后最多剩下多少元钱。如果旅游无法完成，也就是说不存在从景点 出发用不超过 元钱经过不小于 的路程的路线，则该行输出 。

样例输入 1

6 6 3 2
4 1
6 2
2 1
8 1
5 4
9 1
1 2 1
1 3 1
2 4 1
3 5 1
4 6 1
5 6 1
1 12 3
1 9 3

样例输出 1

2
-1

样例解释

T 城的景区和道路如下图所示：

由图可知，从景点 出发，路程为 的路线有两条： 和 。

第 次旅游，最优路线为先在景点 加油，花费 元，此时油量为 ，然后到景点 ，此时油量为 ，在景点 加油，花费 元，此时油量为 ，接着到景点 ，此时油量为 ，最后到景点 ，总路程为 ，最后剩余 元。

第 次旅游，只用 元无论如何也无法走 的路程，因此旅游无法完成。

样例 2

见附加文件（在页面上方下载）中的选手目录下的 trip2.in 与 trip2.ans。

所有测试数据的范围和特点如下表所示：

其中，“特殊性质”一列中的数字意义如下：

• 特殊性质 1：所有 ，，。

• 特殊性质 2：所有 。

• 特殊性质 3：所有 。

对于所有数据，，，，，，，，。