PROGRAMMING:Hearth Stone
Xiao Ming likes to play "furnace stone". The game mainly through playing cards to eliminate strange.
The rule of the game is: players use a card each time to destroy a designated monster. If the card's attack power is greater than or equal to the blood of the designated monster, the attack is successful and the monster is eliminated.
Of course, playing cards also requires a certain amount of mana.
Note: players cannot play more than one card at a time.
Now the question is:
Xiao Ming is currently facing n monsters, each with HP [i]. Xiaoming has m cards at the moment. The attack power of each card is d [i], and the mana value consumed to cooperate with the card is p [i]. At present, the total mana value of Xiao Ming is v.
Excuse me, how many monsters can be eliminated at most with this m card?
###Input format:
The input data first contains an integer T, which represents the number of test cases (T < = 20), and then t sets of test data.
The first line of each group of test data has three integers n, m and V, which represent the number of monsters, the number of cards and the current mana value.
The next line is n integers representing HP [i] of each monster. Next, m lines, two integers in each line, represent the attack power of each card and the mana value d [i], P [i] to be consumed（ 0≤n≤7 , 1≤m,v≤10 , 1≤HP[i],D[i],P[i]≤10)
###Output format:
For each group of tests, output the maximum number of monsters that can be eliminated.
###Input example:
Here is a set of inputs. For example:
```in
two
3 5 7
2 3 3
1 1
2 2
7 5
4 6
2 5
4 5 10
3 1 2 8
2 2
1 1
3 2
5 2
4 3
```
###Output example:
The corresponding output is given here. For example:
```out
two
three
```
Tips
Test 1, available solutions: use the second card (2 2) to destroy the first monster (2), use the third card (7 5) to destroy the second monster (3).
Test 2, available solutions: use the second card (1, 1) to destroy the second monster (1), use the first card (2, 2) to destroy the third monster (2), and use the third card (3, 2) to destroy the first monster (3); After that, the remaining 2 cards cannot be used together< br>
answer：If there is no answer, please comment
The rule of the game is: players use a card each time to destroy a designated monster. If the card's attack power is greater than or equal to the blood of the designated monster, the attack is successful and the monster is eliminated.
Of course, playing cards also requires a certain amount of mana.
Note: players cannot play more than one card at a time.
Now the question is:
Xiao Ming is currently facing n monsters, each with HP [i]. Xiaoming has m cards at the moment. The attack power of each card is d [i], and the mana value consumed to cooperate with the card is p [i]. At present, the total mana value of Xiao Ming is v.
Excuse me, how many monsters can be eliminated at most with this m card?
###Input format:
The input data first contains an integer T, which represents the number of test cases (T < = 20), and then t sets of test data.
The first line of each group of test data has three integers n, m and V, which represent the number of monsters, the number of cards and the current mana value.
The next line is n integers representing HP [i] of each monster. Next, m lines, two integers in each line, represent the attack power of each card and the mana value d [i], P [i] to be consumed（ 0≤n≤7 , 1≤m,v≤10 , 1≤HP[i],D[i],P[i]≤10)
###Output format:
For each group of tests, output the maximum number of monsters that can be eliminated.
###Input example:
Here is a set of inputs. For example:
```in
two
3 5 7
2 3 3
1 1
2 2
7 5
4 6
2 5
4 5 10
3 1 2 8
2 2
1 1
3 2
5 2
4 3
```
###Output example:
The corresponding output is given here. For example:
```out
two
three
```
Tips
Test 1, available solutions: use the second card (2 2) to destroy the first monster (2), use the third card (7 5) to destroy the second monster (3).
Test 2, available solutions: use the second card (1, 1) to destroy the second monster (1), use the first card (2, 2) to destroy the third monster (2), and use the third card (3, 2) to destroy the first monster (3); After that, the remaining 2 cards cannot be used together< br>
answer：If there is no answer, please comment