Problem Description

Farmer John is growing $N$ ($1 \leq N \leq 2\cdot 10^5$) asparagus plants on his farm. However, some plants have genetic differences and grow faster than others. The initial height of plant $i$ is $h_i$ inches, and then every day, plant $i$ grows by $a_i$ inches.

FJ likes some of these plants more. He will give you an array $t_1,\dots,t_N$ consisting of distinct integers; this array contains all integers from $0$ to $N-1$. He wants exactly $t_i$ plants to be taller than plant $i$. Find the minimum number of days needed to satisfy FJ’s requirement, or report that it is impossible.

Input Format

Each test contains multiple test cases.

The first line contains an integer $T$, the number of test cases ($1 \leq T \leq 10$).

For each test case, the first line contains an integer $N$ ($1 \leq N \leq 2\cdot 10^5$), the number of plants.

The second line contains $N$ integers $h_i$ ($1 \leq h_i \leq 10^9$), the initial height of plant $i$.

The third line contains $N$ integers $a_i$ ($1 \leq a_i \leq 10^9$), the height increase per day of plant $i$.

The fourth line contains $N$ distinct integers $t_i$, the array given by FJ.

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

Output Format

Output $T$ lines, each line containing the answer for one test case. If the requirement is impossible to satisfy, output $-1$.

Note that because the integers in this problem can be very large, you may need to use 64-bit integer types (for example, long long in C/C++).

6
1
10
1
0
2
7 3
8 10
1 0
2
3 6
10 8
0 1
2
7 3
8 9
1 0
2
7 7
8 8
0 1
2
7 3
8 8
1 0

0
3
2
5
-1
-1

2
5
7 4 1 10 12
3 4 5 2 1
2 1 0 3 4
5
4 10 12 7 1
3 1 1 4 5
2 4 3 1 0

4
7

Hint

Sample Explanation 1

In the first sample, there are $6$ test cases.

In the first test case, there is only one plant, so the requirement is already satisfied on day $0$.

In the second test case, the first plant needs to be shorter than the second plant. After day $1$, their heights are $15, 13$; after day $2$, their heights are both $23$; after day $3$, their heights are $31, 33$, which is the first day that satisfies the requirement.

The third and fourth test cases are similar to the second test case.

In the fifth test case, both plants start at $7$ inches and both grow by $8$ inches per day, so their heights are always the same. Therefore, the condition can never be satisfied.

In the sixth test case, the initial heights do not satisfy the requirement and the growth rates are the same, so the condition can never be satisfied.

Sample Explanation 2

In the second sample, there are $2$ test cases.

In the first test case, the final heights after day $4$ are $19, 20, 21, 18, 16$.

In the second test case, the final heights after day $7$ are $25, 17, 19, 35, 36$.

Test Point Properties

• Test point $3$ satisfies $N \le 2$.
• Test points $4-5$ satisfy $N \le 50$, and $a_i, h_i \le 10^3$.
• Test points $6-8$ satisfy $N \le 10^3$.
• Test points $9-13$ have no additional constraints.

Translated by ChatGPT 5