题目内容

巡检车要从 $1$ 号驿站赶到 $C$ 号驿站。沿线共有 $C$ 个驿站、$E$ 条双向土路。第 $i$ 条路连接 $x_i$ 与 $y_i$，走过要消耗 $a_i$ 格能量、耗时 $w_i$。

车载电池容量为 $B$，出发时是满的，电量不能超过 $B$。在第 $j$ 号驿站可以一格一格充电，每充 1 格耗时 $s_j$。请计算从 $1$ 赶到 $C$ 的最短时间；若怎么走都到不了，输出 -1。

输入描述

第一行三个整数 $C$、$E$、$B$，表示驿站数、土路数与电池容量（$2\le C\le 10^3$，$1\le E\le 10^4$，$1\le B\le 10^2$）。

第二行 $C$ 个整数 $s_1,s_2,\ldots,s_C$（$0\le s_j\le 10^2$），表示各驿站充 1 格的耗时。

接下来 $E$ 行，每行四个整数 $x_i,y_i,a_i,w_i$（$1\le x_i,y_i\le C$，$1\le a_i\le 10^2$，$1\le w_i\le 10^3$），描述一条双向土路。

输出描述

输出一个整数：赶到 $C$ 号驿站的最短时间。无法到达时输出 -1。

样例1

输入

4 3 5
2 1 9 3
1 2 3 4
2 3 3 5
3 4 2 6

输出

18

说明

出发电量为 5。先走 $1\to 2$（耗时 4，剩 2），在 $2$ 号驿站充 3 格（耗时 3），再走 $2\to 3\to 4$（耗时 5+6）。总时间 18。直接在 $3$ 号驿站用单价 9 充电会更慢。

样例2

输入

2 1 3
1 1
1 2 4 10

输出

-1

说明

唯一一条路要消耗 4 格，超过容量 3，无法通行。

样例3

输入

3 2 4
0 5 1
1 2 2 3
2 3 2 4

输出

7

说明

$1$ 号驿站充电耗时为 0，但出发已经满电，沿 $1\to 2\to 3$ 耗时 3+4=7，不必再充。

数据范围

• $2\le C\le 10^3$
• $1\le E\le 10^4$
• $1\le B\le 10^2$
• $0\le s_j\le 10^2$
• $1\le a_i\le 10^2$
• $1\le w_i\le 10^3$
• 所有输入均为整数