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 自动生成**