AT_tkppc4_1_h.don't be late

在这个世界上，有 $N$ 个车站，编号分别为 $1, 2, 3, \ldots, N$。位于车站 $i$ （其中 $2 \leq i \leq N-1$）时，进行换乘需要花费 $t_i$ 单位时间。此外，车站之间有 $M$ 条线路相连，其中第 $i$ 条线路的特点如下：

• 连接车站 $a_i$ 与车站 $b_i$，可以双向行驶。
• 通过这条线路从车站 $a_i$ 到车站 $b_i$ 或相反方向移动需要 $c_i$ 单位时间。移动时间在任意方向是相同的。
• 电车在该线路上以 $d_i$ 的倍数时刻发车。

Ebishu0309 君由于睡过头，当前时刻为 $0$，他位于车站 $1$。他计划前往车站 $N$。虽然不知道是否可以成功抵达，但如果能在时刻 $K$ 之前抵达，他希望找出一个最早到达的时间。

请帮他判断：能否在时刻 $K$ 之前（包含时刻 $K$）抵达车站 $N$，若是，请计算最早可能到达的时刻；若不能，请输出 $-1$。

输入数据从标准输入读取，格式如下：

$N$ $M$ $K$
$t_2$
$\vdots$
$t_{N-1}$
$a_1$ $b_1$ $c_1$ $d_1$
$\vdots$
$a_M$ $b_M$ $c_M$ $d_M$

如果 Ebishu0309 君可以在时刻 $K$ 之前到达车站 $N$，输出最早的到达时刻。如果不可能抵达，输出 $-1$。

• 所有输入均为整数。
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq K \leq 10^{12}$
• $1 \leq t_i \leq 10^9$ （对于 $2 \leq i \leq N-1$）
• $1 \leq a_i, b_i \leq N$ （对于 $1 \leq i \leq M$ 且 $a_i \neq b_i$）
• $1 \leq c_i$ （对于 $1 \leq i \leq M$）

例子解释

样例解释 1

可以按照以下步骤行动，在时刻 $7$ 抵达目标车站 $3$：

• 时刻 $0$ 从车站 $1$ 出发，使用第 $1$ 条线路到达车站 $2$。
• 在时刻 $3$ 抵达车站 $2$。
• 在车站 $2$ 需要 $2$ 单位时间进行换乘，换乘完成是在时刻 $5$。
• 时刻 $6$ 从车站 $2$ 出发，使用第 $2$ 条线路前往车站 $3$。
• 在时刻 $7$ 抵达车站 $3$。

样例解释 2

Ebishu0309 君至少需要 $9$ 单位时间才能到达车站 $5$，这会超过时刻 $K$，因此输出 $-1$。

样例解释 3

如果 Ebishu0309 君完全无法到达车站 $N$，不仅包括在时刻 $K$ 之前无法到达的情况，还包括无论如何都无法使用电车到达车站 $N$ 的情形，都应该输出 $-1$。

本翻译由 AI 自动生成