PROGRAMMING:Mario Kart
Have you ever played Mario? Of course you do. Who doesn't?! Anyway, a new version of the Mario game has been released. It's some kind of go kart game. You decide to write a program to find your best strategy for completing each stage.
Each horizontal orbit can be simulated as an infinite line, and there are some stations at some specific points on this line. Each station has an integer indicating its position on the orbit. Your task is to move from the first station (the smallest station) to the last station (the largest station).
You can move directly between any two stations (you can go to a station that is not adjacent, or you can go back to a lower station, if you like!) If you have enough promotion gold to complete the action. In each level, you have some promotion coins you can use. Every propulsion coin has cost and energy value. You can choose any subset of coins for each step, but each coin can only be used once at a time. Coins are permanent and you can use them again in other moves of the same level.
To move, you have to choose a subset of add coins so that the sum of their costs cannot exceed L, and the sum of their power values must be exactly equal to the absolute difference between the positions of the two stations you want to move. If there is no such subset, it cannot be moved directly.
Now that you have some levels of configuration, you need to find the minimum number of moves to complete each level, or it is impossible to complete this level.
###Input format:
Your program will be tested on one or more test cases. The first line of input is a single integer T and the number of test cases (1 ≤ t ≤ 100).
Next, there are test cases. The first line of each test case contains three integers, with a single space n ml (2 ≤ n ≤ 100), (1 ≤ m ≤ 100) and (1 ≤ L ≤ 1000), indicating the number of sites, the number of promotion coins and the cost of each action of the maximum total number of coins.
Followed by a line, which contains n separated unique positive integers, by a space (do not need to sort, each integer up to 1000), representing all the stations in the location. Then there are m lines, each line contains 2 integers, separated by a space C V (1 ≤ C, V ≤ 100), representing the cost and power value of a coin respectively.
###Output format:
For each test case, print a line containing a single integer. If it is impossible to transfer from the leftmost workstation to the rightmost workstation, the integer should be - 1. If possible, the integer should be the minimum number of moves.
###Input example:
```in
two
3 2 4
3 1 6
3 2
3 3
3 1 4
1 3 6
3 2
```
###Output example:
```out
two
-1
```
Meaning:
There are n stations along the road, and you have m gold coins. Gold coins have their own costs and values, and can be moved between stations through gold coins;
The total cost should not exceed L, and the sum of its value must be just equal to ABS (I-J);
How many times can I move from station 1 to station n at least?
be careful:
In the first test case, the site location is [3, 1, 6], starting from 1 and ending at 6. You'll have to do two moves,
Use coins from 1 to 3 (3, 2), and use coins from 3 to 6 (3, 3). You can't use (3, 2) and (3, 3) directly from 1 - > 6 because the total cost of coins exceeds the limit of 4.
answer：If there is no answer, please comment
Each horizontal orbit can be simulated as an infinite line, and there are some stations at some specific points on this line. Each station has an integer indicating its position on the orbit. Your task is to move from the first station (the smallest station) to the last station (the largest station).
You can move directly between any two stations (you can go to a station that is not adjacent, or you can go back to a lower station, if you like!) If you have enough promotion gold to complete the action. In each level, you have some promotion coins you can use. Every propulsion coin has cost and energy value. You can choose any subset of coins for each step, but each coin can only be used once at a time. Coins are permanent and you can use them again in other moves of the same level.
To move, you have to choose a subset of add coins so that the sum of their costs cannot exceed L, and the sum of their power values must be exactly equal to the absolute difference between the positions of the two stations you want to move. If there is no such subset, it cannot be moved directly.
Now that you have some levels of configuration, you need to find the minimum number of moves to complete each level, or it is impossible to complete this level.
###Input format:
Your program will be tested on one or more test cases. The first line of input is a single integer T and the number of test cases (1 ≤ t ≤ 100).
Next, there are test cases. The first line of each test case contains three integers, with a single space n ml (2 ≤ n ≤ 100), (1 ≤ m ≤ 100) and (1 ≤ L ≤ 1000), indicating the number of sites, the number of promotion coins and the cost of each action of the maximum total number of coins.
Followed by a line, which contains n separated unique positive integers, by a space (do not need to sort, each integer up to 1000), representing all the stations in the location. Then there are m lines, each line contains 2 integers, separated by a space C V (1 ≤ C, V ≤ 100), representing the cost and power value of a coin respectively.
###Output format:
For each test case, print a line containing a single integer. If it is impossible to transfer from the leftmost workstation to the rightmost workstation, the integer should be - 1. If possible, the integer should be the minimum number of moves.
###Input example:
```in
two
3 2 4
3 1 6
3 2
3 3
3 1 4
1 3 6
3 2
```
###Output example:
```out
two
-1
```
Meaning:
There are n stations along the road, and you have m gold coins. Gold coins have their own costs and values, and can be moved between stations through gold coins;
The total cost should not exceed L, and the sum of its value must be just equal to ABS (I-J);
How many times can I move from station 1 to station n at least?
be careful:
In the first test case, the site location is [3, 1, 6], starting from 1 and ending at 6. You'll have to do two moves,
Use coins from 1 to 3 (3, 2), and use coins from 3 to 6 (3, 3). You can't use (3, 2) and (3, 3) directly from 1 - > 6 because the total cost of coins exceeds the limit of 4.
answer：If there is no answer, please comment