J. Judging Papers
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Panda, a highly respected professor, has submitted $$$n$$$ papers to the International Collegiate Programming Conference. Each paper is judged independently by $$$m$$$ anonymous reviewers who give it a score.

Reviews have seven levels, which correspond to scores:

  • Strong Reject: $$$-3$$$
  • Reject: $$$-2$$$
  • Weak Reject: $$$-1$$$
  • Borderline: $$$0$$$
  • Weak Accept: $$$1$$$
  • Accept: $$$2$$$
  • Strong Accept: $$$3$$$

A paper is accepted if its total score (the sum of all $$$m$$$ reviewer scores) is greater than or equal to a threshold $$$k$$$; otherwise, it is rejected.

After the reviewers submit their scores, there is a rebuttal phase. Panda can select a maximum of $$$b$$$ distinct papers during this phase. A rebuttal is an argument aimed at improving the reviewers' evaluations for a selected paper. However, reviewers react differently, leading to these score changes:

  • Reviewers who gave a high score ($$$1$$$ or higher) will react negatively to the rebuttal; their score is decreased by one level (e.g., $$$3$$$ becomes $$$2$$$, $$$1$$$ becomes $$$0$$$).
  • Reviewers who gave a low score ($$$0$$$ or lower) will react positively to the rebuttal; their score is increased by one level (e.g., $$$-3$$$ becomes $$$-2$$$, $$$0$$$ becomes $$$1$$$).

Panda wants to strategically select at most $$$b$$$ papers for a rebuttal to maximize the final number of accepted papers after all rebuttals are applied.

Input

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

For each test case, the first line contains four integers $$$n, m, k, b$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 10$$$, $$$-30 \le k \le 30$$$, $$$0\le b \le n$$$). $$$n$$$ is the number of papers, $$$m$$$ is the number of reviewers per paper, $$$k$$$ is the acceptance score threshold, and $$$b$$$ is the maximum number of papers that can be selected for a rebuttal.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$m$$$ space-separated integers $$$s_{ij}$$$ ($$$-3 \le s_{ij} \le 3$$$), representing the initial scores given by the $$$j$$$-th reviewer for the $$$i$$$-th paper.

It is guaranteed that $$$\sum n \le 2 \cdot 10^5$$$ over all test cases.

Output

For each test case, output an integer in one line, denoting the maximum number of papers that can be possibly accepted.

Example
Input
2
5 3 2 1
-3 0 3
2 -2 -1
1 1 1
0 0 0
-1 -1 -1
3 2 -1 1
-1 -2
-3 -3
1 -3
Output
2
1