Problem M
Marsneskt erfðaefni

Eins og þú líklega veist að þá má tákna mennskt erfðaefni með löngum streng yfir stafrófið (A, C, G, T), þar sem hvert tákn vísar í mismunandi basa (hvert um sig í þeirri röð sem um var getið; adenín, sýtósín, gúanín og týmín).

Fyrir marsbúa, hinsvegar, eru hlutirnir aðeins öðruvísi. Rannsóknir sem voru framkvæmdar á þeim marsbúa sem var nýlegast fangaður af NASA sýndi að marsneskt erfðaefni samanstendur af heilum $K$ mismunandi bösum! Marsneskt erfðaefni má því tákna með streng yfir $K$ tákna stafróf.

Nú hefur sérstakur rannsóknarhópur, sem hefur áhuga á að nýta marsneskt erfðaefni í gervigreind, beðið um að fá einn samliggjandi bút úr streng af marsnesku erfðaefni. Fyrir $R$ basanna, hafa þeir skilgreind minnsta magn af þeim basa sem þarf að koma fyrir í sýninu þeirra.

Þú hefur áhuga á að finna stysta hlutstreng í erfðaefninu sem uppfyllir skilyrðin.

Inntak

Fyrsta línan inniheldur þrjár heiltölur $N$, $K$ og $R$ sem tákna samtals lengdina á marsneska erfðaefninu, stærðina á stafrófinu og fjölda basa sem rannsakendurnir skilgreindu skilyrði fyrir. Þær uppfylla $1\le R\le K\le N$.

Næsta lína inniheldur $N$ heiltölur aðskildar með bili, sem tákna marsneska erfðaefnis strenginn. Heiltala númer $i$, $D_i$, táknar hvaða basi er í staðsetningu $i$ í strengnum. Basar eru $0$-vísasettir, þ.e. $0\le D_i<K$. Hver einasti basi mun koma allavega einu sinni fyrir í erfðaefnis strengnum.

Hver og ein af næstu $R$ línum inniheldur tvær heiltölur $B$ og $Q$ sem tákna basa og minnsta fjölda sem þarf af þeim basa í sýninu ($0\le B<K,1\le Q\le N$). Hver basi mun ekki koma fyrir oftar en einu sinni í þessum $R$ línum.

Úttak

Skrifaðu út eina heiltölu, lengdina á stysta samliggjandi hlutsreng af erfðaefni sem uppfyllir skilyrði rannsakendanna. Ef ekki er til hlutstrengur sem uppfyllir skilyrðin þá skaltu skrifa út “impossible”.

Takmarkanir

Lausnin þín verður prófuð á einhvern fjölda prufuhópa, hver hópur gefur einhvern fjölda stiga. Hver hópur inniheldur einhvern fjölda prufutilvika. Til að fá stig fyrir hóp þarftu að leysa öll prufutilvik innan hópsins. Lokastigin eru fengin úr skilunum sem gáfu hæst stig.

Útskýringar á sýnidæmum

Í fyrsta sýnidæminu eru þrír hlutstrengir af lengd $2$ sem innihalda einn af hvorum basa en engir hlutstrengir af lengd $1$. Því er stysta lengdin $2$.

Í öðru sýnidæminu er aðeins einn besti hlutstrengur, “1 3 2 0 1 2 0”.

Í þriðja sýnidæminu eru ekki nógu margir basar af týpu 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