← 返回题目列表

AtCoder · kupc2017_i

I. 激活它!

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

分数: 300 点

问题陈述

有 n 魔法石从左到右排成一行。

起初,没有魔法石被激活。

你使用 m 种魔法。如果你使用魔法 i,所有 l_i-th, l_i+1-th, ..., r_i从左边起第一个魔法石被激活。 (已经激活的魔法石也会保持激活状态。)

然而,一旦所有 x_1-th, x_2-th, ..., x_k第-个魔法石被激活,即使你使用更多的魔法也不会再激活更多的魔法石。

你想通过按照你想要的顺序使用每个魔法一次来激活尽可能多的魔法石。

找出你可以激活的魔法石的最大数量。

约束

  • 所有输入值均为整数。
  • 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

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

示例输出 2

9

示例输入 3

6 1 2
2 6
3 4

示例输出 3

2