310231: CF1801D. The way home

D. The way hometime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output 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.

Input

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

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.

Example

Input

4
4 4 2
7 4 3 1
1 2 21
3 2 6
1 3 8
2 4 11
4 4 10
1 2 10 1
1 2 20
2 4 30
1 3 25
3 4 89
4 4 7
5 1 6 2
1 2 5
2 3 10
3 4 50
3 4 70
4 1 2
1 1 1 1
1 3 2

Output

4
24
10
-1

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.

题目大意：
著名的魔术师Borya Budini在穿越由n个城市组成的X国时，不幸在第1个城市遭到抢劫。现在他必须艰难地回家，回到第n个城市。他将通过飞机回家。在这个国家总共有m个航班，第i个航班从城市a_i飞往城市b_i，需要支付s_i个硬币。注意，第i个航班是单程的，所以不能用来从城市b_i回到城市a_i。要乘坐这个航班，Borya必须身处城市a_i，并且至少有s_i个硬币（他将用来支付航班费用）。

在被抢劫后，他只剩下p个硬币，但他并不绝望！身处城市i时，他可以每天组织表演，每场表演会为他带来w_i个硬币。

帮助魔术师找出他是否能够回家，以及他至少需要组织多少场表演。

输入输出数据格式：
输入：
- 第1行包含一个整数t（1≤t≤80）——测试用例的数量。
- 每个测试用例的描述如下：
- 第1行包含三个整数n、m和p（2≤n≤800，1≤m≤3000，0≤p≤10^9）——城市的数量、航班的数量和初始的硬币数量。
- 第2行包含n个整数w_1, w_2, …, w_n（1≤w_i≤10^9）——表演的收益。
- 接下来的m行，每行包含三个整数a_i、b_i和s_i（1≤a_i, b_i≤n，1≤s_i≤10^9）——第i个航班的起始城市、结束城市和费用。

保证所有测试用例的n之和不超过800，m之和不超过10000。

输出：
- 对于每个测试用例，打印一个整数——Borya为了回家至少需要组织的表演数量，或者如果无法回家则打印-1。

示例输入输出：
输入：
```
4
4 4 2
7 4 3 1
1 2 21
3 2 6
1 3 8
2 4 11
4 4 10
1 2 10 1
1 2 20
2 4 30
1 3 25
3 4 89
4 4 7
5 1 6 2
1 2 5
2 3 10
3 4 50
3 4 70
4 1 2
1 1 1 1
1 3 2
```
输出：
```
4
24
10
-1
```题目大意： 著名的魔术师Borya Budini在穿越由n个城市组成的X国时，不幸在第1个城市遭到抢劫。现在他必须艰难地回家，回到第n个城市。他将通过飞机回家。在这个国家总共有m个航班，第i个航班从城市a_i飞往城市b_i，需要支付s_i个硬币。注意，第i个航班是单程的，所以不能用来从城市b_i回到城市a_i。要乘坐这个航班，Borya必须身处城市a_i，并且至少有s_i个硬币（他将用来支付航班费用）。 在被抢劫后，他只剩下p个硬币，但他并不绝望！身处城市i时，他可以每天组织表演，每场表演会为他带来w_i个硬币。 帮助魔术师找出他是否能够回家，以及他至少需要组织多少场表演。 输入输出数据格式： 输入： - 第1行包含一个整数t（1≤t≤80）——测试用例的数量。 - 每个测试用例的描述如下： - 第1行包含三个整数n、m和p（2≤n≤800，1≤m≤3000，0≤p≤10^9）——城市的数量、航班的数量和初始的硬币数量。 - 第2行包含n个整数w_1, w_2, …, w_n（1≤w_i≤10^9）——表演的收益。 - 接下来的m行，每行包含三个整数a_i、b_i和s_i（1≤a_i, b_i≤n，1≤s_i≤10^9）——第i个航班的起始城市、结束城市和费用。 保证所有测试用例的n之和不超过800，m之和不超过10000。 输出： - 对于每个测试用例，打印一个整数——Borya为了回家至少需要组织的表演数量，或者如果无法回家则打印-1。 示例输入输出： 输入： ``` 4 4 4 2 7 4 3 1 1 2 21 3 2 6 1 3 8 2 4 11 4 4 10 1 2 10 1 1 2 20 2 4 30 1 3 25 3 4 89 4 4 7 5 1 6 2 1 2 5 2 3 10 3 4 50 3 4 70 4 1 2 1 1 1 1 1 3 2 ``` 输出： ``` 4 24 10 -1 ```