311181: CF1945F. Kirill and Mushrooms

F. Kirill and Mushroomstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

As soon as everyone in the camp fell asleep, Kirill sneaked out of the tent and went to the Wise Oak to gather mushrooms.

It is known that there are $n$ mushrooms growing under the Oak, each of which has magic power $v_i$. Kirill really wants to make a magical elixir of maximum strength from the mushrooms.

The strength of the elixir is equal to the product of the number of mushrooms in it and the minimum magic power among these mushrooms. To prepare the elixir, Kirill will sequentially pick one mushroom growing under the Oak. Kirill can gather mushrooms in any order.

However, it's not that simple. The Wise Oak informed Kirill of a permutation of numbers $p$ from $1$ to $n$. If Kirill picks only $k$ mushrooms, then the magic power of all mushrooms with indices $p_1, p_2, \dots, p_{k - 1}$ will become $0$. Kirill will not use mushrooms with zero magic power to prepare the elixir.

Your task is to help Kirill gather mushrooms in such a way that he can brew the elixir of maximum possible strength. However, Kirill is a little scared to stay near the oak for too long, so out of all the suitable options for gathering mushrooms, he asks you to find the one with the minimum number of mushrooms.

A permutation of length $n$ is an array consisting of $n$ different integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears in the array twice) and $[1,3,4]$ is also not a permutation ($n=3$, but $4$ appears in the array).

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 200\,000$) — the number of mushrooms.

The second line contains an array $v$ of size $n$ ($1\le v_i \le 10^9$) — the magic powers of the mushrooms.

The third line contains a permutation $p$ of numbers from $1$ to $n$.

It is guaranteed that the sum of the values of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output two integers separated by a space — the maximum strength of the elixir that can be brewed and the minimum number of mushrooms that Kirill needs to use for this.

ExampleInput

6
3
9 8 14
3 2 1
5
1 2 3 4 5
1 2 3 4 5
6
1 2 3 4 5 6
6 5 4 3 2 1
5
1 4 6 10 10
2 1 4 5 3
4
2 2 5 5
4 2 3 1
5
1 2 9 10 10
1 4 2 3 5

Output

16 2
9 3
8 2
20 2
5 1
20 2

Note

In the first example, you need to take the mushrooms with indices $1$ and $2$, so the strength of the elixir is equal to $2 \cdot \min(a_1, a_2) = 2 \cdot \min(9, 8) = 2 \cdot 8 = 16$. Note that the magic power of the mushroom with index $3$ after picking two mushrooms will become $0$.

题目大意：
在营地的人都入睡后，Kirill 偷偷溜出帐篷去智慧橡树那里采摘蘑菇。智慧橡树下长着 n 个蘑菇，每个蘑菇都有魔力值 v_i。Kirill 希望用这些蘑菇制作出力量最大的魔法药水。药水的力量等于药水中的蘑菇数量乘以这些蘑菇中的最小魔力值。Kirill 将依次从橡树下采摘一个蘑菇，他可以以任何顺序采摘蘑菇。然而，智慧橡树告诉了 Kirill 一个由 1 到 n 的数字的排列 p。如果 Kirill 只采摘 k 个蘑菇，那么所有索引为 p_1, p_2, ..., p_{k-1} 的蘑菇的魔力值将变为 0。Kirill 不会使用魔力值为零的蘑菇来制作药水。你的任务是帮助 Kirill 以一种方式采摘蘑菇，使得他能酿造出可能的最大力量的药水。然而，Kirill 有点害怕在橡树旁待得太久，所以请你从所有合适的采摘蘑菇的方式中找出蘑菇数量最少的那一个。

输入数据格式：
每个测试包含多个测试案例。第一行包含一个整数 t (1 ≤ t ≤ 10^4) — 测试案例的数量。接下来是每个测试案例的描述。
每个测试案例的第一行包含一个整数 n (1 ≤ n ≤ 200,000) — 蘑菇的数量。
第二行包含一个大小为 n 的数组 v (1 ≤ v_i ≤ 10^9) — 蘑菇的魔力值。
第三行包含一个由 1 到 n 的数字组成的排列 p。
保证所有测试案例中 n 的值之和不超过 2×10^5。

输出数据格式：
对于每个测试案例，输出两个整数，由一个空格分隔 — 可以酿造的最大力量的药水和 Kirill 为此需要使用的最少蘑菇数量。

示例：
输入：
6
3
9 8 14
3 2 1
5
1 2 3 4 5
1 2 3 4 5
6
1 2 3 4 5 6
6 5 4 3 2 1
5
1 4 6 10 10
2 1 4 5 3
4
2 2 5 5
4 2 3 1
5
1 2 9 10 10
1 4 2 3 5
输出：
16 2
9 3
8 2
20 2
5 1
20 2

注意：
在第一个示例中，你需要采摘索引为 1 和 2 的蘑菇，所以药水的力量等于 2 × min(a_1, a_2) = 2 × min(9, 8) = 2 × 8 = 16。注意，在采摘两个蘑菇后，索引为 3 的蘑菇的魔力值将变为 0。题目大意： 在营地的人都入睡后，Kirill 偷偷溜出帐篷去智慧橡树那里采摘蘑菇。智慧橡树下长着 n 个蘑菇，每个蘑菇都有魔力值 v_i。Kirill 希望用这些蘑菇制作出力量最大的魔法药水。药水的力量等于药水中的蘑菇数量乘以这些蘑菇中的最小魔力值。Kirill 将依次从橡树下采摘一个蘑菇，他可以以任何顺序采摘蘑菇。然而，智慧橡树告诉了 Kirill 一个由 1 到 n 的数字的排列 p。如果 Kirill 只采摘 k 个蘑菇，那么所有索引为 p_1, p_2, ..., p_{k-1} 的蘑菇的魔力值将变为 0。Kirill 不会使用魔力值为零的蘑菇来制作药水。你的任务是帮助 Kirill 以一种方式采摘蘑菇，使得他能酿造出可能的最大力量的药水。然而，Kirill 有点害怕在橡树旁待得太久，所以请你从所有合适的采摘蘑菇的方式中找出蘑菇数量最少的那一个。 输入数据格式： 每个测试包含多个测试案例。第一行包含一个整数 t (1 ≤ t ≤ 10^4) — 测试案例的数量。接下来是每个测试案例的描述。 每个测试案例的第一行包含一个整数 n (1 ≤ n ≤ 200,000) — 蘑菇的数量。 第二行包含一个大小为 n 的数组 v (1 ≤ v_i ≤ 10^9) — 蘑菇的魔力值。 第三行包含一个由 1 到 n 的数字组成的排列 p。 保证所有测试案例中 n 的值之和不超过 2×10^5。 输出数据格式： 对于每个测试案例，输出两个整数，由一个空格分隔 — 可以酿造的最大力量的药水和 Kirill 为此需要使用的最少蘑菇数量。 示例： 输入： 6 3 9 8 14 3 2 1 5 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6 6 5 4 3 2 1 5 1 4 6 10 10 2 1 4 5 3 4 2 2 5 5 4 2 3 1 5 1 2 9 10 10 1 4 2 3 5 输出： 16 2 9 3 8 2 20 2 5 1 20 2 注意： 在第一个示例中，你需要采摘索引为 1 和 2 的蘑菇，所以药水的力量等于 2 × min(a_1, a_2) = 2 × min(9, 8) = 2 × 8 = 16。注意，在采摘两个蘑菇后，索引为 3 的蘑菇的魔力值将变为 0。