Mario Kart

A new version of the Mario game is out, and this one is a kart racing game. Write a program that finds the strategy for finishing each level in the fewest moves.

The track of a level is an infinite straight line with stations at some of its points. Every station sits at an integer position. You start at the station with the smallest position and must reach the station with the largest position in as few moves as possible.

You can move between two stations in one move if you have enough boost coins for it. The destination does not have to be the next station over, and you may go back to a station with a smaller position. Each level gives you a set of boost coins, and every coin has a cost and a power value. For one move you can pick any subset of the coins, but a single coin cannot be used twice in the same move. Coins are permanent, so you can use them again in later moves of the same level.

To make a move you must pick a subset of the boost coins whose total cost is at most $L$ and whose total power is exactly the absolute difference between the positions of the two stations. If no such subset exists, you cannot move between those two stations directly.

You are given the configuration of several levels. For each one, find the minimum number of moves that finishes it, or report that finishing it is impossible.

The first line contains a single integer $T$, the number of test cases. ($1 \le T \le 100$)

The first line of each test case contains three integers separated by single spaces: the number of stations $N$, the number of boost coins $M$, and the largest total cost allowed in one move $L$. ($2 \le N \le 100$, $1 \le M \le 100$, $1 \le L \le 1000$)

The second line contains $N$ distinct positive integers separated by single spaces, the positions of the stations. They are not necessarily sorted, and each position is at most $1000$.

Each of the next $M$ lines contains two integers separated by a single space, the cost $C$ and the power value $V$ of one coin. ($1 \le C, V \le 100$)

For each test case, print one line with a single integer. Print -1 if there is no way to get from the station with the smallest position to the station with the largest position, otherwise print the minimum number of moves.

Take a level whose station positions are 3, 1, 6, with $L = 4$ and two coins, one of cost 3 and power 2 and one of cost 3 and power 3. You start at 1 and must end at 6, so two moves are needed. The power 2 coin takes you from 1 to 3, and the power 3 coin takes you from 3 to 6. Going from 1 straight to 6 would need both coins at once, and their total cost of 6 is over the limit of 4.