Maria's Cakes
By Fabio Lima, Universidade de São Paulo - São Carlos 
Brazil
By Fabio Lima, Universidade de São Paulo - São Carlos Brazil
Maria is an old lady that is retired and makes cakes. She started doing it to help in the family income.
To bake a cake, Maria needs some amount of different ingredients. Each ingredient has a fixed cost per unit. She has D units of cash to spend. Among the cakes types, you need to choose only one type, such that the number of baked cakes is maximal.
Compute the maximum number of cakes of a single type that can be baked.
The first line contains an integer T (T ≤ 100) indicating the number of test cases.
In each test case, the first line contains three integers D (1 ≤ D ≤ 109), I (1 ≤ I ≤ 100) and B (1 ≤ B ≤ 100) indicating the money Maria has, the number of existent ingredients and the quantity of cake types, respectively. In the next line there will be I integers indicating the price of one unit of each ingredient. Then B lines will follow describing each cake. The i-th cake is described as following: a number Qi (1 ≤ Qi ≤ 100) that indicates how many different ingredients are necessary. Follow Qi pairs of numbers indicating the ingredient index and the necessary amount, all in the same line separated by blank spaces.
The amount of each ingredient in a cake will be between 1 and 1000. Each unit of an ingredient will cost between 1 and 1000. The ingredients in the cake description will be unique. The ingredients identifiers will be between 0 and I-1.
For each test output the maximum number of cakes of a single type that can be baked.
| Sample Input | Sample Output |
|
3 10 2 2 3 4 1 0 2 1 1 1 10 4 3 10 10 10 10 3 0 1 1 1 2 1 2 0 1 1 1 1 3 1 100 5 3 6 5 3 8 9 5 2 3 3 5 1 1 0 10 4 1 3 2 10 0 10 4 2 4 4 1 3 1 0 1 1 1 |
2 1 3 |