题目描述

$N$ 人の魔法使いがいて、$1,\ \ldots\ ,N$ と番号付けられています。
魔法使い $i$ の強さは $a_i$ です。また、魔法使い $i$ は強さが $b_i$ のモンスターを倒そうとしています。

あなたは次の操作を何度でも行えます。

• 好きな魔法使いを $1$ 人選び、その強さを $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$

输出格式

答えを出力せよ。

题目大意

有 $n$ 个巫师，第 $i$ 个巫师有 $a_i$ 的法力并计划打败 $b_i$ 法力的怪兽。

构造 $\{A_n\}$，使得对于给定的 $m$ 组 $(x,y)$，均有 $A_x\geqslant b_x,A_y\geqslant b_y$ 或 $A_y\geqslant b_x,A_x\geqslant b_y$。

请最小化 $\sum\limits_{i=1}^n |A_i-a_i|。$

translated by syzf2222

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

2

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

0

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\ \lt\ y_i\ \leq\ N$
• $i\neq\ j$ ならば $(x_i,y_i)\ \neq\ (x_j,y_j)$
• 入力はすべて整数

Sample Explanation 1

魔法使い $1$ と魔法使い $4$ に $1$ 回ずつ操作を行えば最小の操作回数で目的を達成できます。

Sample Explanation 2

$1$ 回も操作を行う必要がありません。