CFCF2193D.Monster Game

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

你收到了一款名为“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 $。

输出格式

对于每个测试用例，输出一个整数——最大的游戏得分。

输入输出样例

输入#1

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

输出#1

3
4
3
8
10000000000

说明/提示

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

首页