#2079. [USACO23DEC] Farmer John Actually Farms B

[USACO23DEC] Farmer John Actually Farms B

题目描述

Farmer John 在他的农场上种植了 NN1N21051 \leq N \leq 2\cdot 10^5) 株芦笋!然而,其中有一些植物存在基因差异,长得比其他植物快。第 ii 株植物的初始高度为 hih_i 英寸,之后每天,第 ii 株植物长高 aia_i 英寸。

FJ 更加钟爱其中的一些植物。他将给你一组由不同整数组成的数组 t1,,tNt_1,\dots,t_N,这个数组包含 00N1N-1 的全部整数。他希望恰好有 tit_i 株植物比第 ii 株植物高。找到最少要经过多少天,才能满足 FJ 的要求,或者报告这个要求是不可能满足的。

输入格式

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

第一行为一个整数 TT,代表测试数据组数(1T101 \leq T \leq 10)。

对于每一组测试数据,第一行一个整数 NN1N21051 \leq N \leq 2\cdot 10^5),表示植物数量。

第二行包含 NN 个整数 hih_i1hi1091 \leq h_i \leq 10^9),表示第 ii 株植物的初始高度。

第三行包含 NN 个整数 aia_i1ai1091 \leq a_i \leq 10^9),表示第 ii 株植物每天增长的高度。

第四行包含 NN 个不同的整数 tit_i,表示 FJ 给你的数组。

保证所有测试数据的 NN 的和不超过 21052\cdot 10^5

输出格式

输出 TT 行,每行表示一组测试数据的答案。如果要求不可能满足,输出 1-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

样例 #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

提示

样例解释 1

在第一组样例中,有 66 组测试数据。

在第一组测试数据中,只有一株植物,所以要求在第 00 天就已经满足。

在第二组测试数据中,需要让第一株植物比第二株植物矮。第 11 天后,它们的高度为 15,1315,13;第 22 天后,它们的高度均为 2323;第 33 天后,它们的高度为 31,3331,33,这是满足要求的第一天。

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

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

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

样例解释 2

在第二组样例中,有 22 组测试数据。

在第一组测试数据中,第 44 天后的最终高度为 19,20,21,18,1619, 20, 21, 18, 16

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

测试点性质

  • 测试点 33 满足 N2N \le 2
  • 测试点 454-5 满足 N50N \le 50ai,hi103a_i, h_i \le 10^3
  • 测试点 686-8 满足 N103N \le 10^3
  • 测试点 9139-13 没有额外限制。