A115472.阈值远征

普及/提高-

官方

通过率：0%

时间限制：1.00s

内存限制：128MB

题目描述

你有 $n$ 把一次性武器，第 $i$ 把武器的威力为 $a_i$ 。共有 $n$ 个关卡，第 $i$ 个关卡需要承受恰好 $b_i$ 次有效攻击后才算通过。

游戏开始前，你可以选择一个难度值 $x$ 。一旦难度确定，所有威力小于 $x$ 的武器都会失效，不能造成任何攻击；其余武器每把至多使用一次。

你按照关卡编号从前往后挑战：

若当前剩余有效武器数量不少于 $b_i$ ，则可以消耗其中任意 $b_i$ 把并通过这一关；
否则游戏立即结束。

你的得分定义为：

$score=x \times(通过的关卡数).$

请你求出最大得分。

输入格式

第一行一个整数 $t$ ，表示测试组数。

对于每组数据：

第一行一个整数 $n$ ；
第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$ ，表示武器威力；
第三行 $n$ 个整数 $b_1,b_2,\dots,b_n$ ，表示各关所需攻击次数。

输出格式

对每组数据输出一个整数，表示最大得分。

输入输出样例

输入#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

说明/提示

数据范围

$1 \le t \le 10^4$
$1 \le n \le 2\times 10^5$
$1 \le a_i \le 10^9$
$1 \le b_i \le n$
所有测试组的 $n$ 之和不超过 $2 \times 10^5$

首页