Фермер Джон вырастил \(N\) (\(1 \leq N \leq 2\cdot 10^5\)) аспарагусов на своей
ферме. Однако некоторые из этих растений имеют генетические отличия, поэтому
некоторые растения растут быстрее чем другие. Изначальная высота \(i\)-го
растения равна \(h_i\) дюймов и после каждого дня \(i\)-ое растение вырастает
на \(a_i\) дюймов.
ФД любит некоторые растения больше чем другие, и он хочет, чтобы некоторые
растения были выше чем другие. Он дал Вам массив различных целых чисел
\(t_1,\dots,t_N\), содержащих все целые числа от \(0\) до \(N-1\) и хочет, чтобы
\(i\)-ое растение имело ровно \(t_i\) растений, которые выше этого. Определите
минимальное количество дней, чтобы требование ФД было удовлетворено или укажите,
что это невозможно.
ФОРМАТ ВВОДА (с клавиатуры):
Первая строка состоит из целого числа \(T\), обозначающего количество
независимых тестов \((1 \leq T \leq 10)\).
Первая строка каждого теста состоит из целого числа \(N\).
Вторая строка состоит из \(N\) целых чисел \(h_i\) \((1 \leq h_i \leq 10^9)\),
обозначающих изначальную высоту \(i\)-го растения в дюймах.
Третья строка состоит из \(N\) целых чисел \(a_i\) \((1 \leq a_i \leq 10^9)\),
обозначающих количество дюймов, на которые \(i\)-ое растение вырастает каждый
день.
Четвёртая строка содержит \(N\) различных целых чисел \(t_i\), обозначающих
массив, который ФД даст Вам.
Гарантируется, что сумма всех \(N\) по всем тестам не превысит \(2\cdot 10^5\).
ФОРМАТ ВЫВОДА (с клавиатуры):
Выведите \(T\) строк, ответ на каждый тест на отдельной строке.
Если невозможно, выведите -1.
Заметим, что тесты этой задачи могут потребовать использования
64-битного целого типа (например, "long long" в C/C++).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|