A. A New Journey
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The assessment plan of HZAUACM consists of two aspects: training contests and problem-solving performance. A total of $$$n$$$ contestants participate in this assessment.

In the training contest assessment process, each contestant will participate in $$$m$$$ training contests. Each training contest has two parameters: base score $$$b$$$ and performance score $$$r$$$. In each training contest, a contestant's single contest score will be calculated as follows:

  • If the contestant did not participate in this training contest, their single contest score for this contest is $$$0$$$.
  • If the contestant participated in this training contest and all contestants who participated in this contest scored $$$0$$$, then the contestant's single contest score for this contest is $$$b$$$.
  • If the contestant participated in this training contest and at least one contestant scored more than $$$0$$$. Let $$$p_i$$$ denote the contestant's score in this contest, and $$$p_{max}$$$ denote the highest score among all contestants in this contest. Then the contestant's single contest score for this contest is $$$\lfloor b + r \times \dfrac{p_i}{p_{max}} \rfloor$$$.

The total score for each contestant in the training contest aspect is the arithmetic average of the highest $$$k$$$ single contest scores obtained from the above $$$m$$$ training contests (i.e., the sum of the highest $$$k$$$ single contest scores divided by $$$k$$$).

Additionally, in the problem-solving performance assessment process, each contestant can earn total points in this aspect by solving problems. If a contestant scores $$$x$$$ in the HZAUACM winter problem set and solves $$$y$$$ additional problems, then their total points in the problem-solving aspect is $$$\lfloor \dfrac{x}{60} + y \rfloor$$$.

Specifically, both the total score in the training contest aspect and the total points in the problem-solving aspect for a contestant are capped at $$$100$$$ points.

If a contestant's total score in the training contest aspect and their total points in the problem-solving aspect are both at least $$$50$$$ points, and either their total score in the training contest aspect is at least $$$60$$$ points or their total points in the problem-solving aspect is at least $$$60$$$ points, then this contestant will become an official member of HZAUACM.

You need to determine how many contestants among the $$$n$$$ will become official members of HZAUACM.

  • $$$\lfloor x \rfloor$$$ denotes the largest integer not exceeding $$$x$$$, for example, $$$\lfloor 4 \rfloor = 4$$$, $$$\lfloor 1.2 \rfloor = 1$$$, $$$\lfloor -2.5 \rfloor = -3$$$.
Input

The input consists of multiple test cases.

First, input a line containing an integer $$$T(1 \leq T \leq 100)$$$, indicating the number of test cases.

For each test case, first input a line with three integers $$$n(1\leq n \leq 2 \times 10^3),m,k(1 \leq k \leq m \leq 2 \times 10^3)$$$, representing the number of contestants, the number of training contests, and the number of contests to consider for the highest score.

Next, input a line with $$$m$$$ integers $$$b_1, b_2, \dots, b_m(0 \leq b_i \leq 100)$$$, representing the base scores for these $$$m$$$ training contests.

Then input a line with $$$m$$$ integers $$$r_1, r_2, \dots, r_m(0 \leq r_i \leq 100)$$$, representing the performance scores for these $$$m$$$ training contests. Additionally, for all $$$r_i$$$, it holds that $$$r_i = 100 - b_i$$$.

Next, input $$$m$$$ lines. For the $$$i^{th}(1\leq i \leq m)$$$ line, input $$$n$$$ integers $$$p_{i1}, p_{i2}, \dots, p_{in}(-1 \leq p_{ij} \leq 100)$$$, where $$$p_{ij}$$$ represents the score of contestant $$$j$$$ in the $$$i^{th}$$$ training contest. If contestant $$$j$$$ did not participate in the $$$i^{th}$$$ training contest, then $$$p_{ij} = -1$$$.

Next, input a line with $$$n$$$ integers $$$x_1, x_2, \dots, x_n(0 \leq x_i \leq 10^4)$$$, where $$$x_i$$$ represents the score of the $$$i^{th}$$$ contestant in the HZAUACM winter problem set.

Finally, input a line with $$$n$$$ integers $$$y_1, y_2, \dots, y_n(0 \leq y_i \leq 100)$$$, where $$$y_i$$$ represents the number of additional problems solved by the $$$i^{th}$$$ contestant.

It is guaranteed that for all data in a test case, the sum of $$$n$$$, the sum of $$$k$$$, and the sum of $$$m$$$ do not exceed $$$2 \times 10^3$$$.

Output

Output a total of $$$T$$$ lines.

For each test case, output an integer indicating the number of contestants who will become official members of HZAUACM.

Example
Input
3
5 4 3
60 50 50 40
40 50 50 60
100 80 90 20 40
40 60 80 -1 80
-1 30 80 -1 90
30 100 20 10 100
3600 2400 1800 200 5000
20 30 35 0 40
5 2 2
60 50
40 50
20 100 0 50 100
-1 -1 -1 -1 -1
3000 2400 4000 200 3600
10 40 30 10 20
5 2 2
60 50
40 50
20 100 0 50 100
0 0 0 0 0
3000 2400 4000 200 3600
10 40 30 10 20
Output
4
2
4
Note

In the first test case, the scores in the first training contest are $$$100, 80, 90, 20, 40$$$, respectively, and the corresponding single contest scores for the contestants are $$$100, 92, 96, 68, 76$$$. Similarly, in the second training contest, the single contest scores are $$$75, 87, 100, 0, 100$$$. In the third training contest, the single contest scores are $$$0, 66, 94, 0, 100$$$. In the fourth training contest, the single contest scores are $$$58, 100, 52, 46, 100$$$. Therefore, the total scores for the contestants in the training contest aspect are $$$77, 93, 96, 38, 100$$$. On the other hand, the total points in the problem-solving aspect are $$$80, 70, 65, 3, 100$$$. Thus, the 1st, 2nd, 3rd, and 5th contestants can become official members of HZAUACM.