题目描述

题目译自 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

数据范围与提示

请注意在 LibreOJ 上共有 $5$ 个子任务，其中第一个子任务为样例。