← 返回题目列表

AtCoder · arc142_e

E. 配对向导

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

有 N 巫师,编号 1, \ldots, N.
向导 i 的实力为 a_i 并计划击败实力为 b_i.

您可以执行以下操作任意次。

  • 增加你选择的任何巫师的力量 1.

一对巫师 i 和向导 j (让我们称这对为 (i, j))据说是 好 当至少满足以下条件之一时。

  • 向导 i 的强度至少为 b_i 和向导 j 的强度至少为 b_j.
  • 向导 i 的强度至少为 b_j 和向导 j 的强度至少为 b_i.

你的目标是使这对 (x_i, y_i) 对每个人都有好处 i=1, \ldots, M.
找到实现它所需的最少操作数。

约束

  • 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),如果 i\neq j.
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

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

示例输出 1

2

向导可以执行一次该操作 1 和向导一次 4 以最少的操作达到目标。


示例输入 2

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

示例输出 2

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

示例输出 3

22