Problem Description

In this world, there are $ N $ stations numbered as $ 1, 2, 3, ..., N $. At station $i\ (2 \leq i \leq N-1)$, it takes $ t_i $ units of time to transfer.
There are also $ M $ routes connecting the stations, where the $ i $-th route is as follows:

• It connects station $ a_i $ and station $ b_i $ bidirectionally.
• It takes $ c_i $ units of time to travel between station $ a_i $ and station $ b_i $ using this route. The travel time is the same in both directions.
• Trains on this route depart at times that are multiples of $ d_i $.

Ebishu0309 woke up late. The current time is $ 0 $, and he is at station $ 1 $.
He wants to go to station $ N $. It is not clear if he can reach station $ N $, but if he can, he wants to do so by time $ K $.

Determine if he can arrive at station $ N $ by time $ K $ (including exactly at time $ K $), and if so, find the earliest time he can arrive.

Input Format

The input is given from the standard input in the following format:

$ 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 $

Output Format

If Ebishu0309 can arrive at station $ N $ before or at time $ K $, output that time in one line.
If it is impossible, output $ -1 $.

Sample Input and Output

Sample Input #1

3 2 821 2 3 42 3 1 2

Sample Output #1

7

Sample Input #2

5 5 82121 2 2 31 3 2 32 5 4 53 4 1 24 5 1 3

Sample Output #2

-1

Sample Input #3

6 2 811112 4 2 35 1 1 2

Sample Output #3

-1

Notes/Hints

Constraints

• All inputs are integers.
• $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 \leq 10^9$ $(1 \leq i \leq M)$

Sample Explanation 1

By moving as follows, he can arrive at station $ 3 $ at time $ 7 $:
- Depart from station $ 1 $ at time $ 0 $. Use the first route to move to station $ 2 $.
- Arrive at station $ 2 $ at time $ 3 $.
- Transfer at station $ 2 $, which takes $ 2 $ units of time. Transfer completes at time $ 5 $.
- Depart from station $ 2 $ at time $ 6 $. Use the second route to move to station $ 3 $.
- Arrive at station $ 3 $ at time $ 7 $.

Sample Explanation 2

Ebishu0309 takes at least $ 9 $ units of time to arrive at station $ 5 $, which is longer than $ K $, so output $ -1 $.

Sample Explanation 3

Ebishu0309 cannot reach station $ N $. Output $ -1 $ not only when he cannot arrive by time $ K $, but also when he cannot reach station $ N $ using the trains at all.

见题面 Input 部分

见题面 Output 部分