Farmer John đang trồng \(N\) cây măng tây (\(1\leq N\leq 2\cdot 10^5\)) trong trang trại! Tuy nhiên, một số cây có khác biệt di truyền nên sẽ sinh trưởng nhanh hơn những cây khác. Chiều cao ban đầu của cây thứ \(i\) là \(h_i\) inch, và sau mỗi ngày, cây thứ \(i\) cao thêm \(a_i\) inch.

FJ thích một số cây hơn những cây khác và muốn một số cây cụ thể cao hơn các cây còn lại. Ông đưa cho bạn một mảng gồm các giá trị đôi một khác nhau \(t_1,\dots,t_N\), chứa tất cả các số nguyên từ \(0\) đến \(N-1\), và muốn cây thứ \(i\) có đúng \(t_i\) cây khác cao hơn nó. Hãy tìm số ngày nhỏ nhất để yêu cầu của FJ được thỏa mãn, hoặc xác định rằng điều đó là không thể.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(T\), biểu thị số bộ test độc lập (\(1\leq T\leq 10\)).

Dòng đầu tiên của mỗi bộ test chứa số nguyên \(N\).

Dòng thứ hai chứa \(N\) số nguyên \(h_i\) (\(1\leq h_i\leq 10^9\)), biểu thị chiều cao ban đầu tính bằng inch của cây thứ \(i\).

Dòng thứ ba chứa \(N\) số nguyên \(a_i\) (\(1\leq a_i\leq 10^9\)), biểu thị số inch mà cây thứ \(i\) cao thêm mỗi ngày.

Dòng thứ tư chứa \(N\) số nguyên đôi một khác nhau \(t_i\), biểu thị mảng mà FJ đưa cho bạn.

Tổng \(N\) trên tất cả các bộ test không vượt quá \(2\cdot 10^5\).

Dữ liệu ra

In \(T\) dòng, mỗi dòng là đáp án cho một bộ test. Nếu không thể, in \(-1\).

Lưu ý rằng các số nguyên lớn trong bài này có thể đòi hỏi kiểu dữ liệu số nguyên 64 bit (ví dụ long long trong C/C++).

Ví dụ

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

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

Phân nhóm

• Dữ liệu 3: \(N\le 2\).
• Dữ liệu 4–5: \(N\le 50\) và \(a_i,h_i\le 10^3\).
• Dữ liệu 6–8: \(N\le 10^3\).
• Dữ liệu 9–13: Không có ràng buộc bổ sung.

Nguồn

USACO 2023 December Contest, Bronze — Farmer John Actually Farms: https://usaco.org/index.php?page=viewproblem2&cpid=1349

Tác giả bài toán: Chongtian Ma