一群 $$$n$$$ 朋友决定去一家餐馆。每个朋友都计划点餐 $$$x_i$$$ burles,总共有 $$$y_i$$$ burles ($$$1 \le i \le n$$$)。
朋友们决定分几天去餐厅。每天,至少有两个朋友组成的一群人去餐厅。每个朋友访问餐厅的次数不超过一次(也就是说,这些组不相交)。这些团体必须满足一个条件,即每个团体的总预算必须不少于团体中的朋友在餐厅消费的金额。换句话说,组中所有 $$$x_i$$$ 值的总和不得超过组中 $$$y_i$$$ 值的总和。
朋友最多可以光顾餐厅多少天?
例如,假设有 $$$n = 6$$$ 朋友,其中 $$$x$$$ = [$$$8, 3, 9, 2, 4, 5$$$] 且 $$$y$$$ = [$$$5, 3, 1, 4, 5, 10$$$]。然后:
- 第一个和第六个朋友可以在第一天去餐厅。他们将在餐厅花费$$$8+5=13$$$ burles,他们的总预算为$$$5+10=15$$$ burles。由于$$$15 \ge 13$$$,他们实际上可以组成一个团体。
- 指数为 $$$2, 4, 5$$$ 的朋友可以组成第二组。他们将在餐厅花费$$$3+2+4=9$$$ burles,他们的总预算将为$$$3+4+5=12$$$ burles ($$$12 \ge 9$$$)。
可以证明,他们将无法组建更多的群组,以便每个群组至少有两个朋友,并且每个群组都可以支付账单。
因此,朋友可以分成的最大组数是 $$$2$$$。朋友们最多可以在餐厅停留两天。请注意,$$$3$$$-rd 的朋友根本不会去这家餐厅。
输出给定 $$$n$$$、$$$x$$$ 和 $$$y$$$ 的情况下朋友可以光顾餐厅的最大天数。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。
测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 朋友的数量。
每个测试用例的第二行恰好包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le 10^9$$$)。 $$$x_i$$$ 的值对应于编号为 $$$i$$$ 的朋友计划在餐厅消费的 burles 数量。
每个测试用例的第三行恰好包含 $$$n$$$ 整数 $$$y_1, y_2, \dots, y_n$$$ ($$$1 \le y_i \le 10^9$$$)。值$$$y_i$$$对应于编号为$$$i$$$的朋友拥有的burles数量。
保证所有测试用例的 $$$n$$$ 值的总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印访问餐厅的最大天数。如果朋友无法组团去餐厅,请打印 0。
示例
输入 #1
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
输出 #1
2 0 1 3 1 3
注意
第一个测试用例在问题陈述中进行了解释。
在第二个测试用例中,朋友不能组成至少一个由两人或多人组成的小组。
在第三个测试用例中,一天内去餐厅的一种方法是与所有三个朋友一起去($$$1+3+10 \ge 2+3+7$$$)。请注意,他们无法选择分成两组。