Farmer John is growing N (1≤N≤2⋅105) 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 ith plant is hi inches, and after each day, the ith plant grows by ai 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 t1,…,tN containing all integers from 0 to N−1 and he wants the ith plant to have exactly ti 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.
INPUT FORMAT (pipe stdin):
The first will consist of an integer T, denoting the number of independent test cases (1≤T≤10).
The first line of each test case consists of an integer N.
The second line consists of N integers hi (1≤hi ≤109) denoting the initial height of the ith plant in inches.
The third line consists of N integers ai (1≤ai≤109) denoting the number of inches the ith plant grows each day.
The fourth line consists of N distinct integers ti denoting the array that FJ gives you.
It is guaranteed that the sum of N over all test cases does not exceed 2⋅105.
OUTPUT FORMAT (pipe stdout):
Output T lines, the answer to each test case on a different line. If it is not possible, output −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++).
SAMPLE INPUT:
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
SAMPLE OUTPUT:
0
3
2
5
-1
-1
In the first sample input, there are 6 test cases.
In the first test case, there is only one plant, so the condition is satisfied on day 0.
In the second test case, we need the first plant to be shorter than the second plant. After day 1, the heights are 15 and 13. After day 2, the heights are both 23. After day 3, the heights are 31 and 33, and that's the first day in which the condition is satisfied.
The third and fourth test cases are similar to the second.
In the fifth test case, both plants start with an initial height of 7 and a growth rate of 8. So they will always have identical heights, and therefore the condition is never satisfied.
In the sixth test case, the condition is not satisfied initially and the growth rates are the same. So the condition can never be satisfied.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
4
7
In the second sample input, 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.
SCORING:
Input 3: N≤2
Inputs 4-5: N≤50 and ai,hi≤103
Inputs 6-8: N≤103
Inputs 9-13: No additional constraints.
Problem credits: Chongtian Ma
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
