← 返回题目列表

Codeforces · 2193/D

D. 怪物游戏

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

您已获得一款名为“Elatyh”的新游戏。在游戏中,您将获得 $$$n$$$ 剑,每把剑都有自己的力量。特别是编号为$$$i$$$的剑,强度为$$$a_i$$$。该游戏由 $$$n$$$ 个级别组成,每个级别都有一个怪物。

您从 $$$1$$$ 级别开始并进一步进步。要通过 $$$i$$$ 关卡并进入 $$$i + 1$$$ 关卡,您需要击败 $$$i$$$ 关卡的怪物。要击败$$$i$$$级别的怪物,你需要用$$$b_i$$$剑攻击它。游戏中的剑非常脆弱,所以只能对付 一 在破坏之前罢工。如果您完成$$$n$$$关卡或用完剑,您可以完成游戏并继续计算分数。

游戏前,您可以选择难度级别。如果你选择难度$$$x$$$,强度小于$$$x$$$的剑不会影响怪物。在这种情况下,游戏得分等于 $$$x$$$ 乘以已完成的关卡数。您的任务是以最大化游戏分数的方式选择游戏难度。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。下面描述测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ $$$(1\le a_i\le 10^9)$$$。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ $$$(1\le b_i\le n)$$$。

保证所有测试用例中 $$$n$$$ 的值之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 最大游戏分数。

示例

输入
复制

5
3
1 3 4
2 1 1
2
2 3
1 1
4
1 2 3 4
2 2 1 1
6
4 4 1 4 5 4
2 2 4 1 2 2
10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1

输出
复制

3
4
3
8
10000000000

注意

考虑第一个测试用例。选择的最佳难度是$$$3$$$。如果难度为$$$3$$$,则可以使用编号为$$$2$$$和$$$3$$$的剑进行攻击。使用 $$$2$$$ 剑可以完成 $$$1$$$ 关卡,因此游戏得分为 $$$3\cdot 1 = 3$$$。