CF1801D.The way home

The famous magician Borya Budini traveled through the country $X$, which consists of $n$ cities. However, an accident happened, and he was robbed in the city number $1$. Now Budini will have a hard way home to the city number $n$.

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.

著名魔术师鲍里亚·布迪尼游历了由 $n$ 座城市组成的国家 $X$。然而，一场意外发生了——他在第 $1$ 号城市遭到了抢劫。如今，布迪尼必须艰难地返回位于第 $n$ 号城市的家。

他将乘坐飞机回家。全国共有 $m$ 班航班，其中第 $i$ 班航班从城市 $a_i$ 飞往城市 $b_i$，票价为 $s_i$ 枚金币。注意：第 $i$ 班航班是单向的，因此无法用于从城市 $b_i$ 前往城市 $a_i$。要乘坐该航班，鲍里亚必须身处城市 $a_i$，且身上至少持有 $s_i$ 枚金币（这些金币将被用于支付机票）。

遭抢劫后，他仅剩下 $p$ 枚金币，但他并未绝望！当他身处城市 $i$ 时，每天都可以举办一场演出，每场演出可为他带来 $w_i$ 枚金币。

请帮助这位魔术师判断他是否能够成功回家，并求出他所需举办的最少演出场数。

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 80$），表示测试用例的数量。随后是各测试用例的描述。

第一行包含三个整数 $n$、$m$ 和 $p$（$2 \le n \le 800$，$1 \le m \le 3000$，$0 \le p \le 10^9$）——分别表示城市数量、航班数量以及初始金币数量。

第二行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$（$1 \le w_i \le 10^9$）——表示在各城市举办演出所获得的收益。

接下来的 $m$ 行每行包含三个整数 $a_i$、$b_i$ 和 $s_i$（$1 \le a_i, b_i \le n$，$1 \le s_i \le 10^9$）——分别表示第 $i$ 个航班的出发城市、到达城市以及花费。

保证所有测试用例中 $n$ 的总和不超过 $800$，且所有测试用例中 $m$ 的总和不超过 $10000$。

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.

对于每个测试用例，输出一个整数——Borya 为回家所需组织的最少演出场次；如果无法回家，则输出 $-1$。

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.

在第一个例子中，Borya 在第一座城市进行 $4$ 场演出是最优策略，最终获得 $2 + 7 \cdot 4 = 30$ 枚金币，然后沿路线 $1-3-2-4$ 行走，花费 $6+8+11=25$ 枚金币。在第二个例子中，Borya 在第一座城市进行 $15$ 场演出，随后飞往第 $3$ 座城市，在那里进行 $9$ 场演出，最后前往第 $4$ 座城市，这是最优策略。