Problem Statement

There are $N$ wizards, numbered $1, \ldots, N$. Wizard $i$ has a strength of $a_i$ and plans to defeat a monster with a strength of $b_i$.

You can perform the following operation any number of times.

• Increase the strength of any wizard of your choice by $1$.

A pair of Wizard $i$ and Wizard $j$ (let us call this pair $(i, j)$) is said to be good when at least one of the following conditions is satisfied.

• Wizard $i$ has a strength of at least $b_i$ and Wizard $j$ has a strength of at least $b_j$.
• Wizard $i$ has a strength of at least $b_j$ and Wizard $j$ has a strength of at least $b_i$.

Your objective is to make the pair $(x_i, y_i)$ good for every $i=1, \ldots, M$. Find the minimum number of operations needed to achieve it.

Constraints

• $2 \leq N \leq 100$
• $1 \leq a_i,b_i \leq 100$
• $1 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq x_i \lt y_i \leq N$
• $(x_i,y_i) \neq (x_j,y_j)$, if $i\neq j$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
\vdots
a_N b_N
M
x_1 y_1
\vdots
x_M y_M

Output

Print the answer.