Problem G
Baba Yaga

Á sinni venjulegu innkaupaferð að grípa stjörnurúnir sá Atli að Baba Yaga væri farin að selja ýmis töfraseyði. Aðspurð hvers vegna hún selur þetta ekki yfirleitt muldrar hún eitthvað um að töfreseyðin séu of voldug fyrir venjulega ferðalanga. Þegar Atli fer að skoða þetta betur sér hann að seyðin hafa ólík áhrif og kosta mismikið, og nóg er úrvalið. Baba Yaga varar hann hins vegar við að svona galdrar eru vandmeðfarnir. Ef hann drekkur tvö seyði sem bæði hafa einhver tiltekin áhrif styttast þau áhrif út og þyrfti hann að sækja sér þriðja seyðið til að bæta upp fyrir það. Atli vill auðvitað vera sem undirbúnastur fyrir það sem á eftir kemur, svo hann veltir því fyrir sér hvort hægt sé að kaupa eitthvað upplag af seyðum sem saman virkja öll möguleg áhrif sem seyðin geta haft og ef svo er, hver ódýrasta leiðin til þess sé.

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur $1 \leq n \leq 10^3$ og $1 \leq b \leq 16$ þar sem $n$ er fjöldi töfraseyða og $b$ er fjöldi ólíkra áhrifa sem þau geta haft. Næst fylgja $n$ lýsingar á töfraseyðum, hver tvær línur. Fyrri línan inniheldur tvær heiltölur $0 \leq c \leq 10^9$ og $1 \leq k \leq b$, kostnaður seyðisins og fjöldi áhrifa sem það hefur. Seinni línan inniheldur $k$ heiltölur $1 \leq b_ i \leq b$, númer áhrifanna sem seyðið hefur.

Úttak

Ef ekki er hægt að virkja öll möguleg áhrif prentið ‘Ekki haegt!’. Annars prentið lágmarkskostnaðinn til að ná því marki.

6 5
10 2
1 3
4 2
1 2
4 2
2 3
10 2
2 5
2 2
4 5
4 1
5

24

3 3
10 2
1 2
10 2
1 3
10 2
2 3

Ekki haegt!

1 3
10 2
1 2

Ekki haegt!