[BalticOI 2018] 火星人的 DNA

**题目译自 [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day1「[Martian DNA](https://boi18-day1-open.kattis.com/problems/boi18.dna)」** 给定一个字符集大小 $|\Sigma| = K$ 的长度为 $N$ 的字符串和 $R$ 个要求，每个要求为使子串中的字符 $B$ 至少出现 $Q$ 次。求出满足所有要求的最短子串长度。

第一行包括三个整数 $N,\, K,\, R$，分别表示字符串的长度、字符集的大小和要求个数，保证 $1\leqslant R\leqslant K\leqslant N$。 第二行包含 $N$ 个用空格隔开的整数，表示这个字符串。字符从 $0$ 开始编号，每个字符集中的字符至少出现一次。 接下来的 $R$ 行，每行两个整数 $B$ 和 $Q$，表示一组要求，满足 $0\leqslant B < K,\, 1\leqslant Q\leqslant N$，同一个字符不会被重复要求两次。

输出一个整数，满足所有要求的最短子串长度。特别地，如果不存在这样的子串，输出 "``impossible``"。

5 2 2
0 1 1 0 1
0 1
1 1

2

13 4 3
1 1 3 2 0 1 2 0 0 0 0 3 1
0 2
2 1
1 2

7

5 3 1
1 2 0 1 2
0 2

impossible

#### 样例 1 解释 有三个长度为 $2$ 的子串含有字符 $0$ 和 $1$ 各一个，分别为 ``0 1``、``1 0`` 和 ``0 1``，但是不存在长度为 $1$ 的子串满足要求，因此满足要求的最短子串的长度为 $2$。 #### 样例 2 解释 最短的满足要求的子串为 ``1 3 2 0 1 2 0``。 #### 样例 3 解释 在这个字符串中，``0`` 的数量不足。 | 子任务 | 分值 | 限制 | |:--------:|:------:|:------:| |$1$ |$16$ |$1\leqslant N\leqslant 100,\, R\leqslant 10$| |$2$ |$24$ |$1\leqslant N\leqslant 4\, 000,\, R\leqslant 10$| |$3$ |$28$ |$1\leqslant N\leqslant 200\, 000,\, R\leqslant 10$| |$4$ |$32$ |$1\leqslant N\leqslant 200\, 000$| 感谢 Hatsune_Miku 提供的翻译