该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

原题为 P9976 [USACO23DEC] Farmer John Actually Farms B

题目描述

杜桥实验中学第114514届马拉松比赛正在进行！

这场比赛总共有 $N(1 \le N \le 2 \times 10^5)$ 个学生参加。根据上一届比赛的排名，他们的出发位置也不同，并且每个选手的速度也不同。

我们假设每个选手都会以匀速完成整场比赛。

具体来说，第 $i$ 个选手的初始位置在 $s_i$，之后的每秒钟他都会跑 $v_i$ 的距离。

现在 Gooby 想要知道，对于第 $i$ 个选手来说，恰好有 $t_i$ 个选手在他前面（不包括并列），Gooby 想要对于每个学生都满足以上情况的时候，最少要经过多少秒，或者这个情况压根就不会发生。

输入格式

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

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

第二行包含 $N$ 个整数 $s_i$（$1 \leq s_i \leq 10^9$），表示第 $i$ 位选手的初始位置。

第三行包含 $N$ 个整数 $v_i$（$1 \leq v_i \leq 10^9$），表示第 $i$ 位选手的速度。

第四行包含 $N$ 个不同的整数 $t_i$，表示 Gooby 想知道的信息。输入保证 $t_1,t_2,\dots,t_N$ 包含 $0$ 到 $N - 1$ 的全部整数。

保证所有测试数据的 $N$ 的和不超过 $2\times 10^5$。

输出格式

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

输入输出样例 #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

输入输出样例 #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

输入输出样例 #3

样例三下载

说明/提示

样例解释 1

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

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

在第二组测试数据中：

• 第1秒过后，他们的路程为 $15, 13$
• 第2秒过后，他们的路程为 $23, 23$，此时对于2号选手来说，有0个人在他前面，但是对于1号选手来说也是0个人在他前面，没有全部满足。
• 第3秒过后，他们的路程为 $31, 33$，此时对于1号选手来说，有1个人在他前面，同时对于2号选手来说，有0个人在他前面，所以满足的最早时间就是3。

在第五组测试数据中，两位选手的初始位置和速度均一致。因此条件永远无法满足。

在第六组测试数据中，2号选手的初始位置落后且速度也不占优势，永远无法超过1号选手，所以条件永远无法满足。

样例解释 2

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

在第一组测试数据中，第 $4$ 秒后的最终路程为 $19, 20, 21, 18, 16$。刚好满足要求。

在第二组测试数据中，第 $7$ 秒后的最终路程为 $25, 17, 19, 35, 36$。刚好满足要求。

测试点性质

• 测试点 $1$ 满足 $N \le 2$。
• 测试点 $2-3$ 满足 $N \le 50$，$s_i, v_i \le 10^3$。
• 测试点 $4-5$ 满足 $N \le 10^3$。
• 测试点 $6-10$ 没有额外限制。