Lýsing

Þú ert fyrirliði keppnisliðs skóla í forritun í Chongqing fyrir CCPC. Til að efla liðsheildina eftir keppnina viltu skipuleggja sameiginlegan kvöldverð. Hins vegar, þar sem fjárhagsáætlunin kláraðist í heitan pott (hotpot) fyrir keppnina, verður kostnaðurinn við máltíðina að skiptast jafnt (það er, ef $k$ manns mæta í máltíð sem kostar alls $W$, borgar hver um sig $\frac{W}{k}$) á milli allra þátttakenda.

Það eru $n$ bekkjarfélagar í liðinu. Hver bekkjarfélagi sem mætir í kvöldverðinn mun panta nákvæmlega einn rétt. $i$-ti bekkjarfélaginn pantar rétt sem kostar $w_i$. Hver bekkjarfélagi hefur einnig fjárhagsþak $r_i$: ef endanlegur deildur kostnaður máltíðarinnar fer yfir $r_i$, mun $i$-ti bekkjarfélaginn vera áfram á hótelinu og panta sér skyndibita í staðinn.

Sem fyrirliði viltu hámarka fjölda bekkjarfélaga sem mæta í kvöldverðinn. Markmið þitt er að velja hlutmengi af $m$ bekkjarfélögum þannig að ef þeir panta hver sinn réttinn, þá fari deildi kostnaðurinn (summa verða $m$ rétta þeirra deilt með $m$) ekki yfir fjárhagsþakið $r_i$ hjá neinum af þessum $m$ völdu bekkjarfélögum. Finndu stærsta mögulega gildið á $m$.

Ef ekkert slíkt hlutmengi er til fyrir $m \ge 1$ skaltu prenta $0$.

Inntak

Það eru mörg prófunartilvik í einni inntaksskrá. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T \le 10^5$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik:

• Fyrsta línan í inntakinu inniheldur eina heiltölu $n$ ($1 \le n \le 10^5$), sem táknar fjölda bekkjarfélaga.
• Næst kemur lína með $n$ heiltölum, þar sem $i$-ta heiltalan $w_i$ ($1 \le w_i \le 10^9$) táknar verð réttarins sem $i$-ti bekkjarfélaginn pantar.
• Síðan kemur lína með $n$ heiltölum, þar sem $i$-ta heiltalan $r_i$ ($1 \le r_i \le 10^9$) táknar hámarksverðið sem $i$-ti bekkjarfélaginn er tilbúinn að borga.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^5$.

Úttak

Fyrir hvert prófunartilvik skaltu prenta línu með einni heiltölu sem táknar svarið.

Dæmi

Sýnidæmi inntak 1

2
5
1 2 3 4 5
5 4 3 2 1
10
3 1 4 1 5 9 2 6 5 3
5 8 9 7 9 3 2 3 8 4

Sýnidæmi úttak 1

3
7