There are n preemptive jobs to be processed on a single machine. Each job j has a processing time p_j and deadline d_j. Preemptive constrains are specified by oriented graph without cycles. Arc (i,j) in this graph means that job i has to be processed before job j. A solution is specified by a sequence of the jobs. For any solution the completion time C_j is easily determined.

The objective is to find the optimal solution in order to minimize

max{C_j-d_j, 0}.

The first line contains a single integer n, 1 ≤ n ≤ 50000. Each of the next n lines contains two integers p_j and d_j, 0 ≤ p_j ≤ 1000, 0 ≤ d_j ≤ 1000000, separated by one or more spaces. Line n+2 contains an integer m (number of arcs), 0 ≤ m ≤ 10*n. Each of the next m lines contains two integers i and j, 1 ≤ i, j ≤ n.

Each of the n lines contains integer i (number of job in the optimal sequence).