AT_kupc2017_i Activate It!!

[problemUrl]: https://atcoder.jp/contests/kupc2017/tasks/kupc2017_i $ n $ 個の魔法石が左右一列に並んでいます。 はじめはどの魔法石も活性化されていません。 $ m $ 種類の魔法があり、$ i $ 種類目の魔法を詠唱すると、左から $ l_i $, $ l_i+1 $, $ ... $, $ r_i $ 番目の魔法石のうち、活性化されていない魔法石が全て活性化されます。 ただし、左から $ x_1 $, $ x_2 $, $ ... $, $ x_k $ 番目の魔法石全てが活性化されると、これ以上魔法を詠唱しても新たに魔法石が活性化されることはありません。 これらの魔法を $ 1 $ つずつ好きな順番で詠唱し、できるだけ多くの魔法石を活性化させたいです。 活性化できる魔法石の個数の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ m $ $ k $ $ x_1 $ $ x_2 $ $ ... $ $ x_k $ $ l_1 $ $ r_1 $ $ l_2 $ $ r_2 $ $ : $ $ l_m $ $ r_m $

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

### 制約 - 入力は全て整数である - $ 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) $ $ (i=1,...,m) $ たちは互いに異なる ### Sample Explanation 1 以下の順に魔法を詠唱すると全ての魔法石を活性化できます。 - $ 2 $ 番目の魔法を詠唱すると、新たに $ 3 $, $ 4 $ 番目の魔法石が活性化される - $ 1 $ 番目の魔法を詠唱すると、新たに $ 1 $, $ 2 $ 番目の魔法石が活性化される - $ 3 $ 番目の魔法を詠唱すると、新たに $ 5 $, $ 6 $, $ 7 $ 番目の魔法石が活性化される