1801D · The way home

Problem: He's going to get there by plane. In total, there are $m$ flights in the country, $i$-th flies from city $a_i$ to city $b_i$ and costs $s_i$ coins. Note that the $i$-th flight is one-way, so it can't be used to get from city $b_i$ to city $a_i$. To use it, Borya must be in the city $a_i$ and have at least $s_i$ coins (which he will spend on the flight).

After the robbery, he has only $p$ coins left, but he does not despair! Being in the city $i$, he can organize performances every day, each performance will bring him $w_i$ coins.

Help the magician find out if he will be able to get home, and what is the minimum number of performances he will have to organize.

Input Format: Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 80$) – the number of test cases. The description of test cases follows.

The first line contains three integers $n$, $m$ and $p$ ($2 \le n \le 800$, $1 \le m \le 3000$, $0 \le p \le 10^9$) — the number of cities, the number of flights and the initial amount of coins.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ $(1 \le w_i \le 10^9)$ — profit from representations.

The following $m$ lines each contain three integers $a_i$, $b_i$ and $s_i$ ($1 \le a_i, b_i \le n$, $1 \le s_i \le 10^9$) — the starting and ending city, and the cost of $i$-th flight.

It is guaranteed that the sum of $n$ over all test cases does not exceed $800$ and the sum of $m$ over all test cases does not exceed $10000$.

Output Format: For each test case print a single integer — the minimum number of performances Borya will have to organize to get home, or $-1$ if it is impossible to do this.

Note: In the first example, it is optimal for Borya to make $4$ performances in the first city, having as a result $2 + 7 \cdot 4 = 30$ coins, and then walk along the route $1-3-2-4$, spending $6+8+11=25$ coins. In the second example, it is optimal for Borya to make $15$ performances in the first city, fly to $3$ city, make $9$ performances there, and then go to $4$ city.