Problem D
Marsvarelsers DNA

Som du antagligen vet kan människans DNA representeras som en lång sträng över ett alfabet med storleken fyra (A, C, G, T), där varje bokstav representerar en viss nukleobas (adenin, cytosin, guanin och thymin).

För marsvarelser fungerar det dock lite annorlunda; forskning utförd på den senaste marsvarelsen som NASA fångat avslöjade att marsvarelsers DNA består av inte mindre än $K$ olika nukleobaser! Deras DNA kan alltså representeras som en sträng över ett alfabet med storleken $K$.

Nu har en forskargrupp, som intresserar sig för att utnyttja marsvarelse-DNA för artificiell intelligens, begärt att få en enda sammanhängande delsträng av en marsvarelses DNA-sträng. För $R$ av nukleobaserna har de specificerat ett minimalt antal av just den nukleobasen som måste finnas i delsträngen.

Du är intresserad av att hitta den kortaste delsträngen av DNAt som uppfyller deras kriterier.

Indata

Första raden innehåller tre heltal $N$, $K$ och $R$: den totala längden på marsvarelsens DNA, alfabetets storlek respektive antalet nukleobaser för vilka forskarna har ett minimumkriterium. Talen uppfyller $1 \le R \le K \le N$.

Den andra raden innehåller $N$ blankstegsseparerade heltal, den kompletta DNA-strängen för marsvarelsen. Det $i$-te av dessa heltal, $D_ i$, talar om vilken nukleobas som finns på den $i$-te positionen i DNA-strängen. Nukleobaserna är $0$-indexerade, d.v.s. de uppfyller $0 \leq D_ i < K$. Varje nukleobas förekommer åtminstone en gång i DNA-strängen.

Var och en av de följande $R$ raderna innehåller två heltal $B$ and $Q$, vilka anger en nukleobas och dess minimalt krävda antal. ($0 \le B < K, 1 \le Q \le N$). Ingen nukleobas kommer att listas mer än en gång på dessa $R$ rader.

Utdata

Skriv ut ett enda heltal, längden på den kortaste sammanhängande delsträngen av DNAt som uppfyller forskarnas krav. Om ingen sådan delsträng finns så skriv ut “impossible”.

Begränsningar

Din lösning kommer att testas på en uppsättning testgrupper, var och en värd en viss poäng. Varje testgrupp innehåller flera testfall. För att få poäng för en testgrupp måste du klara alla testfallen i gruppen. Din slutgiltiga poäng på problemet kommer att vara den maximala poängen av en enda submission.

Förklaring till exemplen

I det första exemplet finns det tre delsträngar med längden $2$ som innehåller en av varje nukleobas (0 respektive 1), nämligen a “0 1”, “1 0” and “0 1”), men inga med längden 1. Alltså är den kortaste längden $2$.

I det andra exemplet är den (unika) optimala delsträngen “1 3 2 0 1 2 0”.

I det tredje exemplet finns det inte tillräckligt med nukleobaser av typ $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