题目描述

在游乐园的「极速飞车」项目前聚集了 $N$ 位游客，由于设备承载能力有限，管理员决定通过竞速赛的方式决定游玩顺序。例如游客 $3$ 在竞速中夺冠，游客 $2$ 获得亚军，游客 $1$ 垫底，则游玩顺序变为 $3 \rightarrow 2 \rightarrow 1$。但部分游客购买了VIP快速通行证，必须严格按指定序号游玩（如游客 $4$ 要求必须第2个游玩，此时顺序变为 $3 \rightarrow 4 \rightarrow 2 \rightarrow 1$）。

现在，管理员的挚友（游客1号）临时需要提前离开，管理员想知道他最早能排到第几个游玩。

注：VIP的游玩次序是固定的，参加竞速赛的游客按照排名先后游玩，没参加竞速赛也不是VIP的游客可以在参加竞速赛的游客之前游玩，但是要保证参加竞速赛的游客严格按照排名顺序游玩。

输入格式

输入共 $K+2$ 行。

第一行包含三个整数 $N,M,K$，表示总游客数、参与竞速赛的游客数、持有VIP通行证的游客数。

第二行包含 $M$ 个不同整数 $m_i$，表示竞速赛排名结果（按游玩顺序从早到晚排列）。

接下来 $K$ 行，每行两个整数 $d_i$ 和 $p_i$，表示游客 $d_i$ 必须第 $p_i$ 个游玩。

保证存在合法解。

输出格式

输出游客1号最早能排到的游玩序号。

样例 #1

样例输入 #1

3 2 1
1 2
3 1

样例输出 #1

2

样例 #2

样例输入 #2

6 3 2
5 4 3
4 3
6 1

样例输出 #2

4

说明/提示

样例解释

样例一：游客1号在竞速赛中排名第一，但游客3号持有VIP并锁定第1位，最终游客1号只能排第2位。

样例二：游客6号锁定第1位，游客4号锁定第3位。竞速赛结果要求5号早于4号游玩，因此5号只能排第2位。游客1号未参与竞速赛，最终最早可排第4位。

数据范围

$1 \leq N \leq 100$，$0 \leq M,K \leq N$，$0 \leq M+K \leq N$
输入数据保证合法且唯一解存在。