Page not loading? Try clicking here.
Placeholder

#6072
Subtask

진짜 농부 1s 1024MB

Problems

헨젤은 그의 농장에서 N (1 \leq N \leq 2\cdot 10^5) 그루의 아스파라거스를 기르고 있습니다! 그러나 그의 식물들 중 일부는 유전적 차이가 있어 일부 식물이 다른 식물보다 빨리 자랄 것입니다. i번째 식물의 초기 높이는 h_i 인치이며, 매일 i번째 식물은 a_i 인치씩 자랍니다.

헨젤은 일부 식물을 다른 식물보다 높게 자라게 하고 싶어합니다. 그는 0에서 N-1까지의 모든 정수를 포함하는 중복되지 않은 값들로 이루어진 배열 t_1,\dots,t_N을 당신에게 주며, 정확히 t_i개의 다른 식물은 i번째 식물보다 키가 커야 합니다. 헨젤의 요청이 만족되기 위한 최소 일수를 찾거나, 불가능하면 그것이 불가능하다고 판단하세요.


Input

첫 번째 줄은 독립적인 테스트 케이스의 수 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로 이루어져 있어 헨젤이 주는 배열을 나타냅니다.

모든 테스트 케이스의 N 합이 2\cdot 10^5를 넘지 않음이 보장됩니다.


Output

T개의 줄을 출력하며, 각각의 테스트 케이스에 대한 답을 출력합니다. 불가능한 경우에는 -1을 출력하세요.

이 문제에서 사용되는 정수의 크기가 크기 때문에 64비트 정수 데이터 유형(예: C/C++에서의 "long long")을 사용해야 할 수 있습니다.


Subtask

# Score Condition
#120

N\le2

#220

N\le50; a_i,h_i\le10^3

#330

N\le10^3

#430

추가 제약 조건 없음


Example #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
0
3
2
5
-1
-1

첫 번째 예제 입력에서는 6개의 테스트 케이스가 있습니다.

첫 번째 테스트 케이스에서는 하나의 식물만 있으므로 조건은 0일 때 이미 충족됩니다.

두 번째 테스트 케이스에서는 첫 번째 식물이 두 번째 식물보다 짧아져야 합니다. 1일 후에 높이는 각각 15와 13입니다. 2일 후에는 높이가 각각 23이 됩니다. 3일 후에 높이가 각각 31과 33이 되며, 이것이 조건이 처음으로 충족되는 날입니다.

세 번째와 네 번째 테스트 케이스는 두 번째 테스트 케이스와 유사합니다.

다섯 번째 테스트 케이스에서는 두 식물이 초기 높이가 모두 7이고 성장률이 8이므로 항상 동일한 높이를 가질 것이며, 따라서 조건은 결코 충족되지 않습니다.

여섯 번째 테스트 케이스에서는 처음에 조건이 충족되지 않으며 성장률이 같습니다. 따라서 조건은 결코 충족되지 않을 것입니다.


Example #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
4
7

두 번째 예제 입력에서는 2개의 테스트 케이스가 있습니다.

첫 번째 테스트 케이스에서는 4일 후에 최종 높이가 각각 19, 20, 21, 18, 16이 됩니다.

두 번째 테스트 케이스에서는 7일 후에 최종 높이가 각각 25, 17, 19, 35, 36이 됩니다.



Source

USACO 2023 December Bronze

You must sign in to write code.