Farmer John Actually Farms

문제

Farmer John is growing $NN$ ($1\le N\le 2\cdot {10}^{5}1\; \backslash leq\; N\; \backslash leq\; 2\backslash cdot\; 10^5$) plants of asparagus on his farm! However some of his plants have genetic differences, so some plants will grow faster than others. The initial height of the $ii$th plant is $h_{i}h\_i$ inches, and after each day, the $ii$th plant grows by $a_{i}a\_i$ inches.

FJ likes some of his plants more than others, and he wants some specific plants to be taller than others. He gives you an array of distinct values $t_1,\dots ,t_{N}t\_1,\backslash dots,t\_N$ containing all integers from $00$ to $N-1N-1$ and he wants the $ii$th plant to have exactly $t_{i}t\_i$ other plants that are taller than it. Find the minimum number of days so that FJ's request is satisfied, or determine that it is impossible.

입력

The first will consist of an integer $TT$, denoting the number of independent test cases $(1\le T\le 10)(1\; \backslash leq\; T\; \backslash leq\; 10)$.

The first line of each test case consists of an integer $NN$.

The second line consists of $NN$ integers $h_{i}h\_i$ $(1\le h_i\le {10}^9)(1\; \backslash leq\; h\_i\; \backslash leq\; 10^9)$ denoting the initial height of the $ii$th plant in inches.

The third line consists of $NN$ integers $a_{i}a\_i$ $(1\le a_i\le {10}^9)(1\; \backslash leq\; a\_i\; \backslash leq\; 10^9)$ denoting the number of inches the $ii$th plant grows each day.

The fourth line consists of $NN$ distinct integers $t_{i}t\_i$ denoting the array that FJ gives you.

It is guaranteed that the sum of $NN$ over all test cases does not exceed $2\cdot {10}^{5}2\backslash cdot\; 10^5$.

출력

Output $TT$ lines, the answer to each test case on a different line. If it is not possible, output $-1-1$.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "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