310240: CF1802F. The way home

F. 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个硬币。请帮助魔术师确定他是否能够回家，以及他至少需要组织多少场表演。

输入输出数据格式：
输入描述：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤80）——测试用例的数量。接下来是测试用例的描述。
第一行包含三个整数n、m和p（2≤n≤800，1≤m≤3000，0≤p≤10^9）——城市的数量、航班的数量和初始的硬币数量。
第二行包含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个硬币。请帮助魔术师确定他是否能够回家，以及他至少需要组织多少场表演。 输入输出数据格式： 输入描述： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤80）——测试用例的数量。接下来是测试用例的描述。 第一行包含三个整数n、m和p（2≤n≤800，1≤m≤3000，0≤p≤10^9）——城市的数量、航班的数量和初始的硬币数量。 第二行包含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