题目内容

巡检队要把一辆巡检车从 1 号站开到 $k$ 号站。值班员必须按油箱容量规划补油，使总用时最短，并把这个时间写入调度单；到不了就记失败。

共有 $k$ 个站点、$e$ 条双向公路。每条公路用四个整数 $a,b,c,t$ 描述：连接 $a$ 与 $b$，耗油 $c$，耗时 $t$ 分钟。出发时油箱是满的，容量为 $q$，油量不能超过 $q$。在站点 $i$ 每补 1 单位油要花 $r_i$ 分钟。

请计算从站点 $1$ 到站点 $k$ 的最短用时；无法到达则输出 -1。

站点数满足 $2 \le k \le 10^3$，公路数满足 $1 \le e \le 10^4$，油箱容量满足 $1 \le q \le 10^2$。各站补油耗时满足 $0 \le r_i \le 10^2$，公路耗油满足 $1 \le c \le 10^2$，公路耗时满足 $1 \le t \le 10^3$，站点编号在 $1 \sim k$ 之间。

输入描述

第一行三个整数 $k$、$e$、$q$（$2 \le k \le 10^3$，$1 \le e \le 10^4$，$1 \le q \le 10^2$），表示站点数、公路数和油箱容量。

第二行 $k$ 个整数 $r_1,r_2,\dots,r_k$（$0 \le r_i \le 10^2$），表示各站每补 1 单位油的分钟数。

接下来 $e$ 行，每行四个整数 $a$、$b$、$c$、$t$（$1 \le a,b \le k$，$1 \le c \le 10^2$，$1 \le t \le 10^3$），表示一条双向公路。

输出描述

输出一个整数，即从站点 $1$ 到站点 $k$ 的最短用时；无法到达则输出 -1。

样例1

输入

3 2 4
4 1 9
1 2 2 3
2 3 2 4

输出

7

说明

出发油量是 4。$1\to 2$ 耗油 2、耗时 3，到达时还剩 2，正好够走 $2\to 3$（耗时 4），总用时 7，中途不用补油。

样例2

输入

2 1 3
2 8
1 2 5 4

输出

-1

说明

唯一一条路要耗油 5，油箱容量只有 3，到不了。

样例3

输入

2 1 3
5 1
1 2 2 8

输出

8

说明

出发油量够直接开过去，用时就是公路上的 8 分钟。