Problem D
DuTub

Du vet att du borde lägga dig vid det här laget! Men du ska bara kolla lite mer på DuTub innan du lägger dig.

Det finns ett antal kategorier du är intresserad av. Varje video på DuTub kan tillhöra en eller flera kategorier. Innan du lägger dig måste du ha sett minst en video i varje kategori. Men du vill förstås inte vara uppe längre än nödvändigt.

Skriv ett program som, givet en lista på videor, beräknar den minsta möjliga tid du måste titta för att ha sett minst en video från varje kategori.

Indata

På första raden står antalet videor $N$. Därefter följer $N$ rader, som beskriver videorna. Vardera av dessa rader innehåller först ett heltal $d_ i$ ($1 \le d_ i \le 900$), videons längd i sekunder, och sedan en sträng som anger de kategorier som videon tillhör. Varje bokstav (som är mellan a och j) betecknar en kategori. Varje video tillhör minst en kategori, och inga kategorier upprepas i en videos beskrivning. Det kan sammanlagt finnas högst 10 olika kategorier.

Utdata

Programmet ska skriva ut det minsta antalet sekunder du behöver spendera på DuTub innan du sett videor ur alla kategorier.

Förklaring av körningsexempel 1

Här finns det totalt 4 kategorier: e, i, g, b, som står för ekorrar, igelkottar, getter och bumbibjörnar. Den tredje videon (g) ger ingenting, för vi måste ändå se den fjärde videon (gb), då den är den enda som innehåller bumbibjörnar. Vi föredrar video 1 framför video 2+5, eftersom dess totala tid är kortare och täcker in båda kategorierna igelkottar och ekorrar. Svaret är alltså 250 sekunder, genom att titta på den första och fjärde videon.

Poängsättning

För testfall värda $20$ poäng gäller $1 \le N \le 10$, och varje video tillhör bara en kategori.
För testfall värda $40$ poäng gäller $1 \le N \le 10$.
För testfall värda $40$ poäng gäller $N = 30$.

5
200 ei
150 e
10 g
50 gb
60 i

250

6
268 abe
271 ca
262 da
145 cd
150 ebc
143 deb

412