题目描述
集训室队员计划去餐馆吃饭。
每个队员都计划花费xi元 点餐,每个人有yi 元预算(1≤i≤n)。
因为餐馆太小
队员们决定把去餐馆的时间分成几天。每天,至少有两个队员结伴去这家餐厅。每个队员去餐厅的次数不超过一次(也就是说,这些小组不相交)。
这些小组必须满足的条件是,每个小组的总预算必须不少于小组中队员在餐厅的花费。换句话说,组中所有xi值的和不能超过组中yi值的和。
集训室队员们最多可以访问这家餐厅几天?
例如,假设有n=6个队员,x = [8,3,9,2,4,5], y =[5,3,1,4,5,10]。然后:
第一个和第六个队员可以在第一天去餐厅。他们将在餐厅花费8+5=13元,他们的总预算是5+10=15元。由于15≥13,所以他们可以组成第一组。
下标为2,4,5的队员可以组成第二组。他们将在餐厅花费3+2+4=9元,他们的总预算将是3+4+5=12元(12≥9)。
可以证明,他们将无法形成更多的组,使每个组至少有两个队员,每个组可以支付账单。
所以,队员最多可以分成2个组。队员们最多可以在餐厅呆两天。注意,第三个队员根本来不了这家餐厅
输入
输入的第一行包含一个整数t(1≤t≤10^4)——测试中测试用例的数量。
下面是对测试用例的描述。
每个测试用例的第一行包含一个整数n(1≤n≤10^5)——朋友的数量。
每个测试用例的第二行正好包含n个整数x1,x2,…,xn(1≤xi≤10^9)。xi的值对应于我编号的朋友计划在餐厅消费钱。
每个测试用例的第三行正好包含n个整数y1,y2,…,yn(1≤yi≤109)。值yi对应编号i的朋友拥有的预算。
输出
对于每个测试用例,打印访问餐厅的最大天数。如果队员们甚至不能组成一个小组去餐馆,打印0。
6
6
8 3 9 2 4 5
5 3 1 4 5 10
4
1 2 3 4
1 1 2 2
3
2 3 7
1 3 10
6
2 3 6 9 5 7
3 2 7 10 6 10
6
5 4 2 1 8 100
1 1 1 1 1 200
6
1 4 1 2 4 2
1 3 3 2 3 4