Gotta Print 'Em All

shoumo Kickoff Programming Conte...
Limits 1s, 512 MB

Gray has received NN documents this morning and he wants to print as many of them as he can within his budget. He hasn't actually set the printing budget yet, but he wonders how many of the NN documents he can print at most if he has a certain budget.

Printing each document requires a piece of paper that costs PP units of money, and some amount of ink. Each of the NN documents has a size of X×YX \times Y, and each of the X×YX\times Y blocks of a document can be empty or can contain an alphanumeric character. If a block is empty, it will be denoted with a dot ('.'). Printing each character requires 1 drop of ink. Each drop of ink costs KK units of money. So, the cost of printing a document will be the total cost of ink for the document and the cost of 1 piece of paper.

For example, the following is a document with a size of 4×34 \times 3:

1c.
...
.0.``````

To print this document, 5 drops of ink and 1 piece of paper will be required.

As we already know the structure of each of the N documents, Gray now has QQ queries to be answered. In each query, he will give a suggested budget and you will have to answer the query by telling him the maximum number of documents he can print within the budget.

Input

The first line contains an integer TT (1T101 ≤ T ≤ 10) - denoting the number of test cases. For each test case:

The first line contains 3 space-separated integers NN, XX, YY (1N1051 ≤ N ≤ 10^5; 1X,Y101 ≤ X, Y ≤ 10), the number of documents and the dimensions of each documents.

The next line contains 2 space-separated integers PP, KK (1K,P1091 ≤ K, P ≤ 10^9) - denoting the cost of a sheet of paper and cost of a drop of ink, respectively.

Then N×XN \times X lines follow, each having YY characters - which define the NN documents. Each character can be an alphabet ('A'-'Z', 'a'-'z') or a digit ('0'-'9') or a dot ('.') The first XX of these lines define the 1st document, the next XX lines define the 2nd document, and so on.

The next line contains a single integer QQ (1Q1051 ≤ Q ≤ 10^5) - denoting number of queries.

Each of the next QQ lines contain an integer BB (1B10141 ≤ B ≤ 10^{14}) - budget for each query.

Output

For each test case, print QQ lines of output, one for each query.

For each query, print a single integer - the maximum number of documents Gray can print so that the cost doesn't exceed the budget for that query.

Sample

InputOutput
2
3 4 3
1 1
z.A
1c.
...
.o.
ABC
123
abc
777
...
...
...
...
5
1
6
20
15
10
1 1 1
1 1
z
1
1
1
1
3
2
2
0

In the first test case of the sample, printing 1st document will cost 6 units (5 for ink and 1 for piece of paper). Similarly, 2nd document costs 13 units and 3rd one costs 1 units.

In 4th query, the budget is 15. With this budget he can either print document 1 and 3 or document 2 and 3. So maximum number of documents printable in this query will be 2.


Submit

Login to submit.

Statistics

85% Solution Ratio
mahdi.hasnatEarliest, Dec '19
ishtupeedFastest, 0.2s
arnob918Lightest, 6.0 MB
habijabiShortest, 713B
Toph uses cookies. By continuing you agree to our Cookie Policy.