分数: 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