题目描述

Farmer John 有 $N$ 头奶牛，编号为 $1$ 到 $N$。经过研究，他发现奶牛的挤奶顺序受到两个关键特性的约束：

1. 社会阶层约束：有 $M$ 头奶牛形成了社会阶层，它们必须按照给定的顺序依次挤奶。也就是说，这些奶牛在挤奶顺序中的相对先后关系必须与给定的顺序一致。
2. 固定位置约束：有 $K$ 头奶牛要求在挤奶顺序中处于某个特定的位置。也就是说，某头奶牛必须恰好排在指定的第几位。

幸运的是，Farmer John 总是能够找到一种满足所有约束的挤奶顺序。

现在，奶牛 $1$ 生病了，Farmer John 想要尽可能早地给奶牛 $1$ 挤奶，以便让她尽快回到牛棚休息。请你帮助 Farmer John 计算出，在所有满足所有约束的挤奶顺序中，奶牛 $1$ 可能出现的最早位置（即排在所有奶牛中的第几位）。

输入格式

第一行包含三个整数 $N, M, K$，分别表示奶牛的总数、有社会阶层约束的奶牛数量、有固定位置约束的奶牛数量。

第二行包含 $M$ 个不同的整数，表示有社会阶层约束的奶牛编号，这些奶牛必须按照给出的顺序依次挤奶。

接下来 $K$ 行，每行包含两个整数 $c_i, p_i$，表示编号为 $c_i$ 的奶牛必须排在第 $p_i$ 位挤奶。

输入数据保证在这些限制之下，至少存在一种符合要求的挤奶顺序。

输出格式

输出一个整数，表示在所有满足约束的挤奶顺序中，奶牛 $1$ 可能出现的最早位置。

样例

6 3 2
4 5 6
5 3
3 1

4

数据范围与提示

• $2 \le N \le 100$
• $1 \le M < N$，$1 \le K < N$
• 给出的奶牛编号均在 $1$ 到 $N$ 之间，且社会阶层约束和固定位置约束中的奶牛编号互不重复（即同一头奶牛不会同时出现在两种约束中，奶牛 $1$ 也不会被固定位置）。
• 保证至少存在一种合法的挤奶顺序。

来源

CSPJ-重点算法班