Asparagus Growth Ordering

Farmer John has planted \( N \) (\(1 \le N \le 2\cdot10^5\)) asparagus plants on his farm. The \( i \)-th plant starts with an initial height of \( h_i \) inches, and it grows by \( a_i \) inches per day.

Farmer John favors some of these plants and has chosen a permutation \( t_1, t_2, \dots, t_N \) of the integers \(0, 1, \dots, N-1\). He requires that, at some day \( d \ge 0 \), for each plant \(i\), exactly \(t_i\) plants are strictly taller than the \(i\)-th plant. In other words, if after \( d \) days the height of plant \( i \) is \( h_i + a_i\,d \), then there must be exactly \( t_i \) plants \( j \) such that \[ h_j + a_j\,d > h_i + a_i\,d. \] Determine the minimum number of days \( d \) needed for Farmer John's requirement to be met, or report that it is impossible.

Explanation: If a plant \( i \) must have exactly \( t_i \) plants taller than itself, then in the sorted order of plants by their height after \( d \) days, plant \( i \) must be the \( (N-t_i)\text{-th} \) smallest (i.e. \( t_i+1 \) th tallest when sorted in descending order). Let the desired position (in increasing order) of plant \( i \) be \( p_i = N-t_i \). Denote by \( x_1, x_2, \dots, x_N \) the plants in order of increasing height after \( d \) days. Then for every two consecutive plants \( x_k \) and \( x_{k+1} \) (with \( k=1,2,\dots,N-1 \)), we must have: \[ h_{x_k} + a_{x_k}\,d < h_{x_{k+1}} + a_{x_{k+1}}\,d. \] This gives rise to constraints on \( d \) which can be reduced to inequalities of the form \[ (a_{x_k} - a_{x_{k+1}})\,d < h_{x_{k+1}} - h_{x_k}. \] Handle each inequality according to whether \(a_{x_k}\) is equal to, less than, or greater than \(a_{x_{k+1}}\). The answer is the minimum integer \( d \ge 0 \) that satisfies all such constraints, or report that no such \( d \) exists by outputting -1.

inputFormat

The input consists of the following:

1. The first line contains an integer \( N \) (\(1 \le N \le 2\cdot10^5\)).
2. The next \( N \) lines each contain two integers \( h_i \) and \( a_i \), giving the initial height and growth rate of the \( i \)-th plant.
3. The last line contains \( N \) space-separated distinct integers \( t_1, t_2, \dots, t_N \), which form a permutation of \(0, 1, \dots, N-1\).

Note that the plants are given in arbitrary order.

outputFormat

Output a single integer: the minimum number of days \( d \) needed to meet the requirement, or -1 if it is impossible.

sample

3
1 1
2 2
3 3
2 1 0

0