题目描述

在一所大型学校里，有 $N$（$1\le N\le 2\times 10^5$）名学生参加了一项特殊的学习计划。每个学生在计划开始时的初始成绩为 $h_i$ 分，并且随着时间的推移，每个学生每天都会以固定的分数提升量 $a_i$ 来提高自己的成绩。

学校的校长对学生的成绩排名有着特定的期望。他给每个学生都制定了一个期望的排名情况，这个情况用一个数组 $t_1,\dots ,t_N$ 来表示，其中包含了 $0$ 到 $N−1$ 的全部整数。对于第 $i$ 个学生，校长希望经过一段时间的学习后，恰好有 $t_i$ 个学生的成绩比他高。

现在，校长想知道最少需要经过多少天，学生们的成绩提升情况才能满足他的期望排名要求。如果无论经过多少天都无法满足这个要求，那就表明这个期望排名是不可能实现的。

输入格式

从文件 $study.in$ 中读入数据。

每个测试点中包含多组测试数据。

第一行为一个整数 $T$，代表测试数据组数（$1 \leq T \leq 10$）。

对于每一组测试数据，第一行一个整数 $N$（$1 \leq N \leq 2\cdot 10^5$），表示学生数量。

第二行包含 $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$。

输出格式

输出答案到文件 $study.out$ 中。

输出 $T$ 行，每行表示一组测试数据的答案。如果要求不可能满足，输出 $-1$。

请注意，由于这个问题涉及的整数大小较大，可能需要使用 64 位整数数据类型（例如，在 C/C++ 中使用 long long 类型）。

输入输出样例 #1

输入 #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

输出 #1

0
3
2
5
-1
-1

样例解释 1

在第一组样例中，有 $6$ 组测试数据。

在第一组测试数据中，只有一个学生，所以要求在第 $0$ 天就已经满足。

在第二组测试数据中，需要让第一个学生比第二个学生的学习成绩低。第 $1$ 天后，它们的学习成绩为 $15,13$；第 $2$ 天后，它们的学习成绩均为 $23$；第 $3$ 天后，它们的学习成绩为 $31,33$，这是满足要求的第一天。

第三组和第四组测试数据与第二组类似。

在第五组测试数据中，两个学生的初始学习成绩均为 $7$ 分，且每天均提升 $8$ 分，所以它们的学习成绩永远相同。因此，条件永远无法满足。

在第六组测试数据中，初始学习成绩不满足要求且增长速度均相同，所以条件永远无法满足。

输入输出样例 #2

输入 #2

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

输出 #2

4
7

样例解释 2

在第二组样例中，有 $2$ 组测试数据。

在第一组测试数据中，第 $4$ 天后的最终学习成绩为 $19, 20, 21, 18, 16$。

在第二组测试数据中，第 $7$ 天后的最终学习成绩为 $25, 17, 19, 35, 36$。

测试点性质

• 测试点 $3$ 满足 $N \le 2$。
• 测试点 $4-5$ 满足 $N \le 50$，$a_i, h_i \le 10^3$。
• 测试点 $6-8$ 满足 $N \le 10^3$。
• 测试点 $9-13$ 没有额外限制。

大样例下载