Panda, erittäin arvostettu professori, on lähettänyt $n$ artikkelia International Collegiate Programming Conference -konferenssiin. Jokaisen artikkelin arvioi riippumattomasti $m$ anonyymiä vertaisarvioijaa, jotka antavat sille pistemäärän.

Arvioissa on seitsemän tasoa, jotka vastaavat seuraavia pistemääriä:

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

Artikkeli hyväksytään, jos sen kokonaispistemäärä (kaikkien $m$ arvioijan pistemäärien summa) on suurempi tai yhtä suuri kuin kynnysarvo $k$; muuten se hylätään.

Kun arvioijat ovat lähettäneet pistemääränsä, seuraa vastinevaihe (rebuttal). Panda voi valita enintään $b$ eri artikkelia tämän vaiheen aikana. Vastine on perustelu, jonka tarkoituksena on parantaa arvioijien arvioita valitusta artikkelista. Arvioijat kuitenkin reagoivat eri tavoin, mikä johtaa seuraaviin pistemuutoksiin:

• Arvioijat, jotka antoivat korkean pistemäärän ($1$ tai korkeampi), reagoivat vastineeseen negatiivisesti; heidän pistemääränsä laskee yhdellä tasolla (esim. $3$ muuttuu luvuksi $2$ ja $1$ muuttuu luvuksi $0$).
• Arvioijat, jotka antoivat matalan pistemäärän ($0$ tai matalampi), reagoivat vastineeseen positiivisesti; heidän pistemääränsä nousee yhdellä tasolla (esim. $-3$ muuttuu luvuksi $-2$ ja $0$ muuttuu luvuksi $1$).

Panda haluaa valita strategisesti enintään $b$ artikkelia vastinetta varten maksimoidakseen hyväksyttyjen artikkelien lopullisen lukumäärän kaikkien vastineiden jälkeen.

Syöte

Ensimmäisellä rivillä on yksi kokonaisluku $T$ ($1 \le T \le 1000$), joka ilmaisee testitapausten lukumäärän.

Jokaisessa testitapauksessa ensimmäisellä rivillä on neljä kokonaislukua $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$ on artikkelien lukumäärä, $m$ on arvioijien lukumäärä artikkelia kohden, $k$ on hyväksymisen pisteraja ja $b$ on vastinetta varten valittavien artikkelien enimmäismäärä.

Seuraavista $n$ rivistä $i$:nnellä on $m$ välilyönnein eroteltua kokonaislukua $s_{ij}$ ($-3 \le s_{ij} \le 3$), jotka kuvaavat $j$:nnen arvioijan $i$:nnelle artikkelille antamia alkuperäisiä pisteitä.

On taattu, että $\sum n \le 2 \cdot 10^5$ yli kaikkien testitapausten.

Tuloste

Tulosta jokaiselle testitapaukselle yhteen riviin kokonaisluku, joka ilmaisee hyväksyttävissä olevien artikkelien enimmäismäärän.

Esimerkit

Syöte 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

Tuloste 1

2
1