题目描述

题目译自 BalticOI 2018 Day1「Martian 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 提供的翻译