Panda, một giáo sư rất được kính trọng, đã nộp $n$ bài báo cho Hội nghị Lập trình Sinh viên Quốc tế (International Collegiate Programming Conference). Mỗi bài báo được đánh giá độc lập bởi $m$ phản biện ẩn danh và mỗi người sẽ cho một điểm số.

Đánh giá có bảy mức, tương ứng với các điểm số sau:

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

Một bài báo được chấp nhận nếu tổng điểm của nó (tổng điểm của tất cả $m$ phản biện) lớn hơn hoặc bằng ngưỡng $k$; ngược lại, nó sẽ bị từ chối.

Sau khi các phản biện gửi điểm số, sẽ có một giai đoạn phản hồi (rebuttal). Panda có thể chọn tối đa $b$ bài báo phân biệt trong giai đoạn này. Phản hồi là một lập luận nhằm cải thiện đánh giá của các phản biện đối với bài báo được chọn. Tuy nhiên, các phản biện lại phản ứng theo những cách khác nhau, dẫn đến những thay đổi điểm số như sau:

• Những phản biện đã cho điểm cao (từ $1$ trở lên) sẽ phản ứng tiêu cực với phản hồi; điểm của họ bị giảm đi một mức (ví dụ: $3$ thành $2$, $1$ thành $0$).
• Những phản biện đã cho điểm thấp (từ $0$ trở xuống) sẽ phản ứng tích cực với phản hồi; điểm của họ được tăng lên một mức (ví dụ: $-3$ thành $-2$, $0$ thành $1$).

Panda muốn chọn một cách chiến lược nhiều nhất $b$ bài báo để gửi phản hồi nhằm tối đa hóa số lượng bài báo cuối cùng được chấp nhận sau khi tất cả các phản hồi được áp dụng.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $T$ ($1 \le T \le 1000$), biểu thị số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa bốn số nguyên $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$). Trong đó $n$ là số lượng bài báo, $m$ là số lượng phản biện cho mỗi bài báo, $k$ là ngưỡng điểm chấp nhận, và $b$ là số lượng bài báo tối đa có thể được chọn để gửi phản hồi.

Dòng thứ $i$ trong $n$ dòng tiếp theo chứa $m$ số nguyên cách nhau bởi dấu cách $s_{ij}$ ($-3 \le s_{ij} \le 3$), biểu thị điểm số ban đầu do phản biện thứ $j$ chấm cho bài báo thứ $i$.

Dữ liệu đảm bảo rằng $\sum n \le 2 \cdot 10^5$ trên tất cả các bộ dữ liệu.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy in ra một số nguyên trên một dòng, biểu thị số lượng bài báo tối đa có thể được chấp nhận.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2
1