← 返回题目列表

Codeforces · 1443/C

C. 交付困境

中文机器翻译题面 查看原题

Petya 正在准备他的生日。他决定餐桌上有$$$n$$$不同的菜肴,编号从$$$1$$$到$$$n$$$。由于 Petya 不喜欢做饭,所以他想在餐馆点这些菜。

不幸的是,所有菜肴都是在不同的餐厅准备的,因此 Petya 需要从 $$$n$$$ 不同的地方取餐。为了加快这一过程,他想在一些餐馆订购快递送货服务。因此,对于每道菜,Petya 有两种选择:

- 菜肴将由快递员从餐厅 $$$i$$$ 送达,在这种情况下,快递员将在 $$$a_i$$$ 分钟内到达,
- Petya 自己去餐厅 $$$i$$$ 并拿起菜肴,他将花费 $$$b_i$$$ 分钟在这上面。

每家餐厅都有自己的快递员,他们在 Petya 离开家的那一刻就开始送货。换句话说,所有快递员都是并行工作的。 Petya 必须访问所有他没有选择送货的餐厅,他始终如一地这样做。

例如,如果Petya想要点$$$n = 4$$$菜肴​​,$$$a = [3, 7, 4, 5]$$$,$$$b = [2, 1, 2, 4]$$$,那么他可以从第一家和第四家餐厅叫外卖,自己去第二家和第三家餐厅。那么第一家餐厅的快递员将在 $$$3$$$ 分钟内送达订单,第四家餐厅的快递员将在 $$$5$$$ 分钟内送达订单,Petya 将在 $$$1 + 2 = 3$$$ 分钟内取走剩余的菜肴。因此,$$$5$$$ 分钟后,所有菜肴都会送到 Petya 的家里。

求所有菜肴可以送达 Petya 家的最短时间。

输入

第一行包含一个正整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例都以一行开头,其中包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — Petya 想要点的菜品数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1 \ldots a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 编号为 $$$i$$$ 的菜肴的快递递送时间。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1 \ldots b_n$$$ ($$$1 \le b_i \le 10^9$$$) - Petya 拿起编号为 $$$i$$$ 的菜肴的时间。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 所有菜肴都可以到达 Petya 家的最短时间。

示例

输入 #1

4
4
3 7 4 5
2 1 2 4
4
1 2 3 4
3 3 3 3
2
1 2
10 10
2
10 10
1 2

输出 #1

5
3
2
3