B"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. Each test consists of multiple test cases. The first line contains a single integer t ( 1 <= t <= 80 ) xe2 x80 x93 the number of test cases. The description of test cases follows. The first line contains three integers n , m and p ( 2 <= n <= 800 , 1 <= m <= 3000 , 0 <= p <= 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 <= w_i <= 10^9) -- profit from representations. The following m lines each contain three integers a_i , b_i and s_i ( 1 <= a_i, b_i <= n , 1 <= s_i <= 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 . 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. 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"...