Nông Trại Của FJ

Nông dân John trồng $N$ cây với chiều cao ban đầu $h_1,h_2,\dots ,h_N$ và tốc độ tăng trưởng hàng ngày $a_1,a_2,\dots ,a_N$. Sau $d$ ngày, chiều cao của cây thứ $i$ là $h_i+d·a_i$.

Nông dân John muốn mỗi cây $i$ có đúng $t_i$ cây khác cao hơn nó (tức là cây $i$ đứng ở vị trí $t_i+1$ khi sắp xếp chiều cao giảm dần, các $t_i$ phân biệt đôi một). Hãy tìm số ngày tối thiểu cần thiết để đạt được cấu hình này, hoặc xác định nếu không thể.

Lưu ý: Tại thời điểm đó, không có hai cây nào có cùng chi���u cao.

Dữ liệu vào

• Dòng $1$: Số nguyên $T$ ($1\le T\le 10$) — số bộ test.
• Với mỗi bộ test:
  • Dòng $1$: Số nguyên $N$ ($1\le N\le 2·{10}^5$).
  • Dòng $2$: $N$ số nguyên $h_1,\dots ,h_N$ ($1\le h_i\le {10}^9$).
  • Dòng $3$: $N$ số nguyên $a_1,\dots ,a_N$ ($1\le a_i\le {10}^9$).
  • Dòng $4$: $N$ số nguyên phân biệt $t_1,\dots ,t_N$ ($0\le t_i\le N-1$).

Dữ liệu ra

In ra $T$ dòng, mỗi dòng là số ngày tối thiểu cần thiết, hoặc $-1$ nếu không thể.

Ràng buộc

• Tổng $N$ qua tất cả các bộ test $\le 2·{10}^5$.
• Cần sử dụng kiểu dữ liệu 64-bit.
• Test $3$: $N\le 2$.
• Các test $4$-$5$: $N\le 50$.
• Các test $6$-$8$: $N\le {10}^3$.
• Các test $9$-$13$: Không có ràng buộc thêm.

Ví dụ