Problem Description

There are $ n $ magic stones arranged in a row from left to right.

Initially, none of the magic stones are activated.

There are $ m $ types of magic spells. When the $ i $-th type of magic is cast, all non-activated magic stones from the $ l_i $-th to the $ r_i $-th (inclusive) from the left are activated.

However, once all the magic stones at positions $ x_1 $, $ x_2 $, $ ... $, $ x_k $ from the left are activated, no new magic stones can be activated by casting more spells.

You want to cast these magic spells in any order you like, to activate as many magic stones as possible.

Find the maximum number of magic stones that can be activated.

Input Format

The input is given from the 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 Format

Output the maximum number of magic stones that can be activated in one line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

7

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

Notes/Hints

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$
• $ (l_i, r_i) $ for $ i=1,...,m $ are all distinct.

Sample Explanation 1

All magic stones can be activated by casting the spells in the following order:
- Cast the 2nd spell, which activates the 3rd and 4th magic stones.
- Cast the 1st spell, which activates the 1st and 2nd magic stones.
- Cast the 3rd spell, which activates the 5th, 6th, and 7th magic stones.

见题面 Input 部分

见题面 Output 部分