Problem D
Marsboer-DNA

Som du kanskje vet så kan menneskelig DNA representeres som en lang streng over et alfabet på størrelse 4 (A, C, G, T), hvor hvert symbol representerer en forskjellig nukleobase (henholdsvis adenine, cytosine, guanine, og thymine).

For marsboere derimot, så er ting litt annerledes. Forskning utført på en marsboer som NASA har fanget har vist at marsboer-DNA består av hele $K$ forskjellige nukleobaser! Marsboer-DNA kan dermed representeres som en streng over et alfabet med størrelse $K$.

En forskningsgruppe ønsker å utnytte marsboer-DNA til utviklingen av kunstig intelligens og vil i den sammenhengen få tak i en sammenhengende del av DNA strengen til en marsboer. For $R$ av nukleobasene har de spesifisert et minimumsantall av hvor mange instanser av den nukleobasen de trenger i strengen.

Du ønsker å finne den korteste substrengen fra marsboer-DNAet som tilfredstiller kravene til forskningsgruppen.

Input

Første linje inneholder 3 heltall, $N$, $K$, og $R$, som beskriver henholdsvis den totale lengden på marsboerens DNA, størrelsen av alfabetet, og antall nukleobaser som forskerene har spesifisert et minstekrav for antallet av. Disse tilfredsstiller $1 \le R \le K \le N$.

Andre linje inneholder $N$ heltall andskilt med mellomrom, som representerer hele DNA-strengen til marsboeren. Det $i$-te av disse heltallene, $D_ i$, indikerer hvilken nukleobase som er på den $i$-ende posisjonen i DNA-strengen. Nukleobasene er $0$-indekserte. Dvs. $0 \leq D_ i < K$. Hver nukleobase vil opptre minst én gang i DNA strengen.

Hver av de neste $R$ linjene inneholder to heltall $B$ og $Q$ som representerer henholdsvis en nukleobase og dens minste påkrevde antall ($0 \le B < K, 1 \le Q \le N$). Ingen nukleobase vil være nevnt mer enn én gang i disse $R$ linjene.

Output

Skriv ut et enkelt heltall, lengden av den korteste sammenhengende substrengen med DNA som tilfredsstiller forskerenes krav. Dersom ingen slik substreng eksisterer, skriv ut “impossible”.

Begrensninger

Løsningen din vil bli testet på et sett av testgrupper, hver verdt et visst antall poeng. Hver testgruppe inneholder et sett av tester. For å få poeng for en testgruppe må du løse alle testene i den gruppen. Din endelige poengsum vil være den høyeste poengsummen du har fått på en enkelt innlevering.

Eksempelforklaring

I det første eksempelet så er det tre substrenger av lengde $2$ som inneholder en av hver av nukleobasene 0 og 1 (nemlig “0 1”, “1 0” and “0 1”), men ingen substreng av lengde $1$. Dermed er den korteste lengden $2$.

I det andre eksempelet er den (unike) optimale substrengen “1 3 2 0 1 2 0”.

I det tredje eksempelet så er det ikke nok nukleobaser av type 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