题目描述

C 国有 n 个城市和 m 条双向通行的道路，每条道路连接某两个不同的城市。任意两个城市之间可能有若干条道路直接相连。

C 国幅员辽阔，各地的资源分布情况各不相同，导致环境和舒适度有所差异。

同时，由于 C 国在积极改善生活，所以每个城市都设置了一个落脚点，使得途经每个城市的时候人们都可以休息，从而恢复一定的体力。当然，每个人都有自己的体力上限，当体力达到这个上限时，无论他再如何休息，体力都不会再增加。

商人阿龙来到 C 国旅游。当他得知这一信息之后，便决定在旅游的同时，根据得到的信息，实时调整自己的作息，使得通行时间缩短。设 C 国 n 个城市的标号从 1∼n，阿龙决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行。

例如，假设 C 国有 5 个大城市，城市的编号和道路连接情况如下图，每条边都是双向通行的道路。

阿龙在 1 号城市出发，初始体力值为 4。

在图中所示的五个城市中：

• 1 号城市提供的落脚点可以让阿龙每 2 分钟恢复 1 体力
• 2 号城市提供的落脚点可以让阿龙每 3 分钟恢复 1 体力
• 3 号城市提供的落脚点可以让阿龙每 1 分钟恢复 1 体力
• 4 号城市提供的落脚点可以让阿龙每 10 分钟恢复 1 体力
• 5 号城市提供的落脚点可以让阿龙每 3 分钟恢复 1 体力

除此之外，每条边的信息为：

• 1-2 之间通行需要花费 1 分钟，阿龙需要消耗 4 体力
• 1-4 之间通行需要花费 3 分钟，阿龙需要消耗 3 体力
• 2-3 之间通行需要花费 1 分钟，阿龙需要消耗 2 体力
• 3-5 之间通行需要花费 1 分钟，阿龙需要消耗 1 体力
• 4-5 之间通行需要花费 1 分钟，阿龙需要消耗 3 体力

假设阿龙的体力上限为 6，阿龙可以选择：

• ① 从 1 出发到达 2 号城市，耗费 4 的体力，1 分钟的时间；之后在 2 号城市休息 6 分钟，恢复 2 的体力；从 2 出发到达 3 号城市，耗费 2 的体力，1 分钟的时间；之后在 3 号城市休息 1 分钟，恢复 1 体力；之后从 3 出发到达 5 号城市，花费 1 的体力，耗费 1 的时间。共花费了 10 分钟的时间。
• ② 从 1 出发到达 4 号城市，耗费 3 的体力，3 分钟的时间；之后在 4 号城市休息 20 分钟，恢复 2 的体力；从 4 号城市出发，耗费 3 的体力，1 分钟的时间，最终到达 5 号城市，一共花费 24 分钟的时间。
• ③ 在 1 号城市休息 4 分钟，恢复 2 的体力；之后从 1 出发到达 3 号城市，耗费 3 体力，花费 3 分钟的时间；之后从 3 城市出发到达 5 号城市，耗费 3 的体力，花费 1 分钟的时间。最终到达 5 号城市。一共花费 8 分钟的时间。
• 可以发现，③方案是最优的。

现在给你该国的地图，请你帮阿龙计算，从 1 号城市到达 n 号城市的最少通行时间。

输入格式

• 第一行输入 n, m, T, maxT,分别代表 C 国有 n 个城市，m 条道路，当前阿龙的体力 T，阿龙体力上限 maxT。
• 接下来一行有 n 个数 ti，第 i 个整数代表在 i 号城市落脚点休息时，每 ti 分钟恢复1体力。
• 接下来 m 行，每行有四个数 ai,bi,wi,vi，分别代表一条道路 ai<-->bi，通过该道路所需的体力 wi 和所需时间 vi。

输出格式：

一个整数，表示阿龙从 1 号城市到 n 号城市花费的最短时间。

输入样例

4 3 100 100
10 10 1 10
1 2 40 10
2 3 40 10
3 4 40 10

输出样例

50

数据说明

没有负权边，所有数据都是整数;

数据范围：w ≤ maxT ≤ 200, 1 ≤ ti ≤ 200, 1 ≤ vi ≤ 100

• 对于20%的数据, n ≤ 10, m ≤ 50
• 对于40%的数据, n ≤ 50, m ≤ 1000
• 对于50%的数据, n ≤ 200, m ≤ 10000
• 对于100%的数据, n ≤ 1000, m ≤ 100000