備受尊敬嘅 Panda 教授向國際大學生程式設計研討會（International Collegiate Programming Conference）提交咗 $n$ 篇論文。每篇論文都會由 $m$ 位匿名審稿人獨立評審並畀出分數。

評審共有七個等級，對應以下分數：

• Strong Reject（強烈拒絕）：$-3$
• Reject（拒絕）：$-2$
• Weak Reject（傾向拒絕）：$-1$
• Borderline（臨界）：$0$
• Weak Accept（傾向接受）：$1$
• Accept（接受）：$2$
• Strong Accept（強烈接受）：$3$

如果一篇論文嘅總分（全部 $m$ 位審稿人分數嘅總和）大過或等於門檻值 $k$，呢篇論文就會被接受；否則就會被拒絕。

喺審稿人提交分數之後，會有一個答辯（rebuttal）階段。Panda 喺呢個階段最多可以揀 $b$ 篇唔同嘅論文。答辯係一段旨在改善審稿人對所選論文評價嘅論述。不過，唔同審稿人會有唔同反應，導致分數出現以下變化：

• 畀出高分（$1$ 分或以上）嘅審稿人會對答辯產生負面反應；佢哋嘅評分會降低一個等級（例如 $3$ 變成 $2$，$1$ 變成 $0$）。
• 畀出低分（$0$ 分或以下）嘅審稿人會對答辯產生正面反應；佢哋嘅評分會提高一個等級（例如 $-3$ 變成 $-2$，$0$ 變成 $1$）。

Panda 希望有策略咁揀出最多 $b$ 篇論文進行答辯，令到所有答辯生效之後最終被接受嘅論文數量達到最大。

輸入格式

第一行包含一個整數 $T$（$1 \le T \le 1000$），代表測試資料嘅組數。

對於每組測試資料，第一行包含四個整數 $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$ 係論文數量，$m$ 係每篇論文嘅審稿人數量，$k$ 係接受論文嘅分數門檻，而 $b$ 係最多可以揀嚟進行答辯嘅論文數量。

接落嚟 $n$ 行之中嘅第 $i$ 行包含 $m$ 個用空格隔開嘅整數 $s_{ij}$（$-3 \le s_{ij} \le 3$），代表第 $j$ 位審稿人對第 $i$ 篇論文畀出嘅初始分數。

題目保證所有測試資料入面 $\sum n \le 2 \cdot 10^5$。

輸出格式

對於每組測試資料，喺一行入面輸出一個整數，代表最終可能被接受嘅最大論文數量。

範例

輸入 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

輸出 1

2
1