I - Activate It!! Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

n 個の魔法石が左右一列に並んでいます。

はじめはどの魔法石も活性化されていません。

m 種類の魔法があり、i 種類目の魔法を詠唱すると、左から l_i, l_i+1, ..., r_i 番目の魔法石のうち、活性化されていない魔法石が全て活性化されます。

ただし、左から x_1, x_2, ..., x_k 番目の魔法石全てが活性化されると、これ以上魔法を詠唱しても新たに魔法石が活性化されることはありません。

これらの魔法を 1 つずつ好きな順番で詠唱し、できるだけ多くの魔法石を活性化させたいです。

活性化できる魔法石の個数の最大値を求めてください。

制約

  • 入力は全て整数である
  • 1 \leq n \leq 10^5
  • 1 \leq m \leq 10^5
  • 1 \leq k \leq n
  • 1 \leq l_i \leq r_i \leq n
  • 1 \leq x_1 < x_2 < ... < x_k \leq n
  • (l_i, r_i) (i=1,...,m) たちは互いに異なる

入力

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

n m k
x_1 x_2 ... x_k
l_1 r_1
l_2 r_2
:
l_m r_m

出力

活性化できる魔法石の個数の最大値を一行で出力せよ。

入力例1

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

出力例1

7

以下の順に魔法を詠唱すると全ての魔法石を活性化できます。

  • 2 番目の魔法を詠唱すると、新たに 3, 4 番目の魔法石が活性化される
  • 1 番目の魔法を詠唱すると、新たに 1, 2 番目の魔法石が活性化される
  • 3 番目の魔法を詠唱すると、新たに 5, 6, 7 番目の魔法石が活性化される

入力例2

10 4 1
6
1 2
4 5
2 7
5 10

出力例2

9

入力例3

6 1 2
2 6
3 4

出力例3

2

Score : 300 points

Problem Statement

There are n magic stones aligned in a line from left to right.

At first, no magic stones are activated.

You use m kinds of magic. If you use magic i, all the l_i-th, l_i+1-th, ..., r_i-th magic stones from the left get activated. ( Magic stones which are already activated also keep activated. )

However, once all the x_1-th, x_2-th, ..., x_k-th magic stones are activated, no more magic stones get activated even if you use more magic.

You want to activate as many magic stones as possible by using each magic exactly once in any order you want.

Find the maximum number of magic stones you can activate.

Constraints

  • All input values are integers.
  • 1 \leq n \leq 10^5
  • 1 \leq m \leq 10^5
  • 1 \leq k \leq n
  • 1 \leq l_i \leq r_i \leq n
  • 1 \leq x_1 < x_2 < ... < x_k \leq n
  • (l_i, r_i) (i=1,...,m) is distinct from each other.

Input

Input is given from Standard Input in the following format:

n m k
x_1 x_2 ... x_k
l_1 r_1
l_2 r_2
:
l_m r_m

Output

Print the maximum number of magic stones you can activate.

Sample Input 1

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

Sample Output 1

7

You can activate all the magic stones by using magic in the following order.

  • Use the second magic, and the third and fourth magic stones get activated.
  • Use the first magic, and the first and second magic stones get activated.
  • Use the third magic, and the fifth, sixth, and seventh magic stones get activated.

Sample Input 2

10 4 1
6
1 2
4 5
2 7
5 10

Sample Output 2

9

Sample Input 3

6 1 2
2 6
3 4

Sample Output 3

2

Source Name

KUPC2017