CF1801D.The way home
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 ai to city bi and costs si coins. Note that the i -th flight is one-way, so it can't be used to get from city bi to city ai . To use it, Borya must be in the city ai and have at least si 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 wi 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 ) – 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≤109 ) — the number of cities, the number of flights and the initial amount of coins.
The second line contains n integers w1,w2,…,wn (1≤wi≤109) — profit from representations.
The following m lines each contain three integers ai , bi and si ( 1≤ai,bi≤n , 1≤si≤109 ) — 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.
输入输出样例
输入#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
输出#1
4 24 10 -1
说明/提示
In the first example, it is optimal for Borya to make 4 performances in the first city, having as a result 2+7⋅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.