20860번 - 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.

På första raden står antalet videor $N$ ($1 ≤ N ≤ 30$). 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. 

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