题目描述

有 $N$ 个魔法使，编号为 $1,\ldots,N$。
魔法使 $i$ 的强度为 $a_i$。此外，魔法使 $i$ 正在试图击败强度为 $b_i$ 的怪物。

你可以进行如下操作任意次：

• 任选一名魔法使，其强度增加 $1$。

对于魔法使 $i$ 和魔法使 $j$ 的一对（下称为“配对 $(i,j)$”），如果满足以下两个条件中的至少一个，则称其为好配对：

• 魔法使 $i$ 的强度不小于 $b_i$，且魔法使 $j$ 的强度不小于 $b_j$；
• 魔法使 $i$ 的强度不小于 $b_j$，且魔法使 $j$ 的强度不小于 $b_i$。

你的目标是使得对于所有 $i=1,\ldots,M$，配对 $(x_i,y_i)$ 都是好配对。
请你求出为达成目标所需的最小操作次数。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

请输出答案。

样例 1

输入

5
1 5
2 4
3 3
4 2
5 1
3
1 4
2 5
3 5

输出

2

样例 2

输入

4
1 1
1 1
1 1
1 1
3
1 2
2 3
3 4

输出

0

样例 3

输入

9
1 1
2 4
5 5
7 10
9 3
9 13
10 9
3 9
2 9
7
1 5
2 5
1 6
2 4
3 4
4 9
8 9

输出

22

说明/提示

限制条件

• $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 < y_i \leq N$
• 若 $i \neq j$，则 $(x_i, y_i) \neq (x_j, y_j)$
• 所有输入均为整数

样例解释 1

只需分别对魔法使 $1$ 和魔法使 $4$ 各进行一次操作，即可用最少的操作次数达成目标。

样例解释 2

无需进行任何操作。

由 ChatGPT 4.1 翻译