题目描述

Farmer john 在他的农场上种植了 $N$ 株芦笋!

然而，其中有一些植物存在基因差异，长得比其他植物快。

第$i$株植物的初始高度为 $h_i$英寸，之后每天第$i$株植物长高$a_i$英寸。

FJ 更加钟爱其中的一些植物。

他将给你一组由不同整数组成的数组$t_1...t_N$，这个数组包含$0$到$N -1$的全部整数。

他希望恰好有$t_i$株植物比第$i$株植物高。

找到最少要经过多少天，才能满足 FJ 的要求，或者报告这个要求是不可能满足的。

输入

第一行为一个整数 $T$，代表测试数据组数

第二行包含 $N$ 个整数 $h_i$，表示第$i$株植物的初始高度。

第三行包含 $N$ 个整数 $a_i$，表示第$i$株植物每天增长的高度。

第四行包含 $N$ 个不同的整数 $t$，表示FJ给你的数组。

保证所有测试数据的 $N$ 的和不超过 $2.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

样例解释

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

在第一组测试数据中，只有一株植物，所以要求在第 0天就已经满足， 在第二组测试数据中，需要让第一株植物比第二注植物矮。第1天后，它们的高度为 15,13;第2天后，它们的高度均为 23:第 3天后，它们的高度为 31.33，这是满足要求的第一天。

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

在第五组测试数据中，两株植物的初始高度均为7英寸，且每天均增长8英寸，所以它们的高度永远相同。因此，条件永远无法满足。

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

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

样例解释

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

在第一组测试数据中，第 4 天后的最终高度为 19,20,21,18.16.

在第二组测试数据中，第7天后的最终高度为 25,17,19,35,36。

提示

$1 \leq T \leq 10$

$1 \leq h_i,a_i \leq 10^9$

测试点3满足$N \leq 2$

测试点4-5满足$n \leq 50,a_i,h_i \leq 10^3$

测试点6-8满足 $N \leq 10^3$

测试点9-13没有额外限制.