Problem G
Marsjańskie DNA

Jak pewnie wiesz, ludzkie DNA może być reprezentowane jako długie słowo nad alfabetem złożonym z czterech liter (A, C, G, T), gdzie każdy symbol reprezentuje różną zasadę azotową nukleotydu (odpowiednio: adeninę, cytozynę, guaninę i tyminę).

W przypadku marsjan sytuacja jest trochę inna; badania prowadzone nad ostatnim marsjaninem złapanym przez NASA ujawniły, że marsjańskie DNA składa się z oszałamiającej liczby $K$ różnych zasad nukleotydów! Marsjańskie DNA może zatem być reprezentowane jako słowo nad alfabetem o rozmiarze $K$.

Teraz pewna grupa badawcza, która jest zainteresowana wykorzystaniem marsjańskiego DNA w sztucznej inteligencji, zgłosiła zapotrzebowanie na pewien spójny fragment marsjańskiego DNA. Dla $R$ zasad nukleotydów wymagają oni, aby każda z tych zasad występowała co najmniej pewną liczbę razy w tej próbce.

Chciałbyś znaleźć najkrótsze podsłowo marsjańskiego DNA, które spełnia te wymagania.

Wejście

Pierwszy wiersz zawiera trzy liczby całkowite $N$, $K$ i $R$, oznaczające odpowiednio długość marsjańskiego DNA, rozmiar alfabetu oraz liczbę zasad nukleotydów, dla których badacze określili minimalne zapotrzebowanie. Zachodzi $1 \le R \le K \le N$.

Drugi wiersz zawiera opis łańcucha DNA w postaci $N$ liczb całkowitych oddzielonych pojedynczymi odstępami Liczba na $i$-tym miejscu, $D_ i$, oznacza numer zasady nukleotydu na $i$-tej pozycji w łańcuchu DNA. Numery zasad są indeksowane od $0$, tj. $0 \leq D_ i < K$. Każda z zasad wystąpi w łańcuchu DNA co najmniej raz.

Każdy z kolejnych $R$ wierszy zawiera po dwie liczby całkowite $B$ i $Q$, oznaczające odpowiednio numer oraz minimalne zapotrzebowanie na daną zasadę ($0 \le B < K, 1 \le Q \le N$). Wśród tych $R$ linii żadna zasada nie wystąpi więcej niż raz.

Wyjście

Wypisz pojedynczą liczbę całkowitą równą długości najkrótszego spójnego podciągu DNA, który spełnia warunki naukowców. Jeżeli taki podciąg nie istnieje, wypisz ,,impossible”.

Ograniczenia

Zestaw testów dzieli się na kilka grup, każda jest warta pewną liczbę punktów. Każda grupa składa się z jednego bądź większej liczby testów. Aby otrzymać punkty za daną grupę, Twoje rozwiązanie musi przejść wszystkie testy z tej grupy. Ostateczny wynik za zadanie jest liczony jako maksymalny wynik z pojedynczych zgłoszeń.

Wyjaśnienie do przykładów

W pierwszym przykładzie, mamy trzy spójne podciągi o długości $2$ które zawierają co najmniej po jednej zasadzie 0 i 1 (tj. “0 1”, “1 0” and “0 1”), ale nie ma spójnego podciągu o długości $1$. Najkrótsza długość wynosi zatem $2$.

W drugim przykładzie, optymalny (i jednoznaczny) spójny podciąg to ”1 3 2 0 1 2 0”.

W trzecim przykładzie, nie ma wystarczająco dużo zasad typu 0.

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