E - Pairing Wizards Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

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) が良いペアであるようにすることです。
目的を達成するために必要な操作の回数の最小値を求めてください。

制約

  • 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)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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 に 1 回ずつ操作を行えば最小の操作回数で目的を達成できます。

入力例 2

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

出力例 2

0

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

入力例 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

Score : 900 points

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.

Sample Input 1

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

Sample Output 1

2

You can perform the operation once for Wizard 1 and once for Wizard 4 to achieve the objective with the fewest operations.

Sample Input 2

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

Sample Output 2

0

No operation is needed.

Sample Input 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

Sample Output 3

22