תיאור הבעיה

אתה ראש צוות של נבחרת תכנות בית-ספרית בצ'ונגצ'ינג לתחרות ה-CCPC. כדי לחזק את הגיבוש הקבוצתי לאחר התחרות, ברצונך לארגן ארוחת ערב קבוצתית. עם זאת, מאחר שהתקציב אזל על הוט-פוט (Hotpot) לפני התחרות, יש לחלק את עלות הארוחה שווה בשווה (כלומר, אם $k$ אנשים משתתפים בארוחה שעלותה הכוללת היא $W$, כל אדם משלם $\frac{W}{k}$) בין כל המשתתפים.

ישנם $n$ חברי כיתה בצוות. כל חבר כיתה שמשתתף בארוחת הערב יזמין בדיוק מנה אחת. חבר הכיתה ה-$i$ מזמין מנה שעלותה $w_i$. לכל חבר כיתה יש גם מגבלת תקציב $r_i$: אם העלות המשותפת הסופית של הארוחה תעלה על $r_i$, חבר הכיתה ה-$i$ יישאר במלון ויזמין משלוח במקום זאת.

כראש הצוות, ברצונך למקסם את מספר חברי הכיתה המשתתפים בארוחת הערב. מטרתך היא לבחור תת-קבוצה של $m$ חברי כיתה כך שאם כל אחד מהם יזמין את המנה שלו, העלות המשותפת (סכום מחירי $m$ המנות שלהם חלקי $m$) לא תעלה על התקציב $r_i$ של אף אחד מ-$m$ חברי הכיתה שנבחרו. מצא את הערך המקסימלי האפשרי של $m$.

אם לא קיימת תת-קבוצה כזו עבור $m \ge 1$, הדפס $0$.

קלט

ישנם מספר מקרי בדיקה בקובץ קלט אחד. השורה הראשונה של הקלט מכילה מספר שלם בודד $T$ ($1 \le T \le 10^5$), המציין את מספר מקרי הבדיקה.

עבור כל מקרה בדיקה:

• השורה הראשונה של הקלט מכילה מספר שלם בודד $n$ ($1 \le n \le 10^5$), המייצג את מספר חברי הכיתה.
• בשורה הבאה נתונים $n$ מספרים שלמים, כאשר המספר השלם ה-$i$, $w_i$ ($1 \le w_i \le 10^9$), מייצג את מחיר המנה שהזמין חבר הכיתה ה-$i$.
• בשורה שלאחריה נתונים $n$ מספרים שלמים, כאשר המספר השלם ה-$i$, $r_i$ ($1 \le r_i \le 10^9$), מייצג את המחיר המקסימלי שחבר הכיתה ה-$i$ מוכן לשלם.

מובטח כי סכום ה-$n$-ים על פני כל מקרי הבדיקה אינו עולה על $10^5$.

פלט

עבור כל מקרה בדיקה, הדפס שורה עם מספר שלם בודד המייצג את התשובה.

דוגמה

קלט לדוגמה 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

פלט לדוגמה 1

3
7