本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

农夫约翰在他的农场里种了 $N$（$1 \leq N \leq 2\cdot 10^5$）株芦笋！然而其中一些植株存在基因差异，因此有些植株会比其他植株长得更快。第 $i$ 株植株的初始高度为 $h_i$ 英寸，并且每天结束后，第 $i$ 株植株会增长 $a_i$ 英寸。

FJ 更喜欢其中一些植株，他希望某些特定植株比其他植株更高。他给你一个由互不相同的数构成的数组 $t_1,\dots,t_N$，其中包含从 $0$ 到 $N-1$ 的所有整数，并且他希望第 $i$ 株植株恰好有 $t_i$ 株其他植株比它更高。请找出满足 FJ 要求所需的最少天数，或者判断这是不可能的。

输入格式

第一行包含一个整数 $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$，表示 FJ 给你的数组。

保证所有测试用例的 $N$ 之和不超过 $2\cdot 10^5$。

输出格式

输出 $T$ 行，每行对应一个测试用例的答案。若不可能满足要求，输出 $-1$。

注意：本题涉及的整数可能很大，可能需要使用 64 位整数类型（例如 C/C++ 中的 "long long"）。

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

提示

在第一组样例输入中，有 6 个测试用例。 在第一个测试用例中，只有一株植株，因此在第 0 天就满足条件。 在第二个测试用例中，我们需要第一株植株比第二株植株矮。第 1 天后，高度分别为 15 和 13。第 2 天后，高度分别为 23 和 23。第 3 天后，高度分别为 31 和 33，而这就是第一次满足条件的那一天。 第三和第四个测试用例与第二个类似。 在第五个测试用例中，两株植株的初始高度都是 7，生长速度都是 8。因此它们将始终具有相同的高度，所以条件永远无法满足。 在第六个测试用例中，初始时条件不满足且生长速度相同，所以条件永远无法满足。

在第二组样例输入中，有 2 个测试用例。 在第一个测试用例中，第 4 天后的最终高度分别为 19、20、21、18、16。 在第二个测试用例中，第 7 天后的最终高度分别为 25、17、19、35、36。

评分（SCORING）： Input 3: $N \le 2$ Inputs 4-5: $N \le 50$ 且 $a_i, h_i \le 10^3$ Inputs 6-8: $N \le 10^3$ Inputs 9-13: 无额外限制。 题目致谢：Chongtian Ma

来源

USACO|2023|Bronze