D - DobyvateľČasový limit: 2s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] Dobyvateľ Jano už dobyl skoro všetko, no niečo predsa len nie. Nedobyté ostalo srdce nedobytnej Júlie. Júlia však nie je taká nedobytná, ako sa na prvý pohľad zdá. Je len veľmi vyberavá. Júliin vyvolený musí spĺňať určité kritériá. Keďže dobyvateľ Jano si vydobyl dobré kontakty, podarilo sa mu Júliin zoznam kritérií získať. Júlia má na zozname niekoľko kritérií. Keďže však nechce ostať celý život sama, uvedomuje si, že nie je v silách žiadneho človeka ich splniť všetky. Preto má na zozname tiež kombinácie kritérií, ktoré postačujú na to, aby si nápadník získal jej priazeň. Jano pre každé jej kritérium odhadol počet týždňov, ktoré potrebuje na to, aby dané kritérium splnil. Teraz rozmýšľa, na ktorých kritériách pracovať, aby Júliu získal čo najskôr. Jano je sebavedomý a tak verí, že na kritériách dokáže pracovať paralelne. ÚlohaDaný je zoznam Júliiných kritérií, pre každé z nich Janov odhad a kombinácie kritérií, ktoré stačia na dobytie Júlie. Úlohou je vypočítať najkratší čas, v ktorom vie Jano splniť všetky kritéria niektorej z kombinácií.VstupPrvý riadok vstupu obsahuje počet testovacích sád T (1≤T≤100). Každá testovacia sada pozostáva z dvoch samostatných riadkov. Prvý riadok obsahuje Janove odhady oddelené čiarkami. Každý odhad je zapísaný ako názov kritéria, dvojbodka, a celé číslo reprezentujúce počet týždňov, za ktoré vie Jano toto kritérium splniť. Názov kritéria je neprázdny reťazec pozostávajúci len zo znakov malej anglickej abecedy ('a' až 'z'), nie dlhší ako 20 znakov. Každý odhad je v rozmedzí 0..1000 (vrátane). Môžete predpokladať, že kritérií je najviac 20. Druhý reťazec obsahuje kombinácie kritérií (aspoň jednu, no nanajvýš 10 kombinácií). Kombinácie sú oddelené znakom '|' a kritériá v rámci jednej kombinácie sú oddelené znakom '&'. Každá kombinácia obsahuje aspoň jedno kritérium a žiadne neobsahuje dvakrát.VýstupPre každú testovaciu sadu by výstup mal obsahovať minimálny počet týždňov, za ktorý vie dobyvateľ Jano Júliu dobyť.PríkladVstup2 bohaty:0,vysportovany:400,inteligentny:50,dobrevyzerajuci:1000,tolerantny:800 bohaty&dobrevyzerajuci|inteligentny&bohaty|dobrevyzerajuci&vysportovany&tolerantny xy:14,y:10,zxy:25 xy&y|y&zxy Výstup50 14Príklad prevzatý z IDI Open 2007. |