Šeštadieninė informatikos olimpiadininkų mokykla

Labirintas yra orientuoto medžio pavidalo. Kiekvienoje labirinto aklavietėje paslėpta po vieną tam tikros vertės brangakmenį.

Labirinte galima eiti tik tolyn nuo įėjimo (t. y. rodyklėmis parodytomis kryptimis). Iš kiekvienos kryžkelės išeina vienas arba daugiau kelių. Į kiekvieną kryžkelę ir aklavietę veda tik vienas kelias.

Yra tik vienas įėjimas į labirintą.

Paveiksle pateikto labirinto pavyzdyje kryžkelės pažymėtos skrituliukais, aklavietės – kvadratėliais, kuriuose įrašyta čia paslėpto brangakmenio vertė. Įėjimas į labirintą pažymėtas žvaigždute.

Berniukas eina į labirintą pasiimti vieno brangakmenio, suprantama, kuo didesnės vertės. Jį lydi labirinto šeimininkas, kuris nori, kad būtų paimtas kuo mažesnės vertės brangakmenis. Berniukas ir šeimininkas susitinka labirinto įėjime. Kiekvienoje kryžkelėje reikia pasirinkti, kuriuo keliu bus keliaujama toliau (aišku, jei yra daugiau kaip vienas kelias). Įėjime renkasi berniukas, kitoje kryžkelėje (į kurią abu pateko po berniuko pasirinkimo) – šeimininkas, dar kitoje – vėl berniukas ir taip toliau. Šeimininkas labai gerai žino labirintą, tad bet kurioje kryžkelėje gali pasirinkti, kuriuo labirinto keliu jam naudingiausia vesti.

Parašykite programą, kuri nustatytų, kokios didžiausios vertės brangakmenį gali paimti berniukas, jeigu labirinto šeimininkas kelią rinksis optimaliai.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje pateikiamas kryžkelių skaičius N ir aklaviečių skaičius M. Visada yra bent viena kryžkelė (įėjimas) ir bent viena aklavietė. Skaičių M ir N suma neviršija 10000. Kryžkelėms yra duoti unikalūs numeriai (sveiki skaičiai) iš intervalo [1;10000].

Toliau byloje įrašyta N+M eilučių. Kiekviena eilutė nusako arba kryžkelę, arba aklavietę. Šios N+M eilučių faile pateiktos bet kokia tvarka.

Kryžkelę k nusakanti eilutė prasideda raide „K“. Jei ši kryžkelė yra labirinto įėjimas, tuomet po raidės „K“ eina nulis (0), jei į ją patenkama iš kitos kryžkelės, tuomet rašomas pastarosios numeris. Paskutinysis skaičius eilutėje – kryžkelės k numeris.

Kiekviena aklavietę nusakanti eilutė prasideda raide „A“. Toliau įrašyti du sveikieji skaičiai: kryžkelės, iš kurios ateinama į šią aklavietę numeris bei joje esančio brangakmenio vertė v (v – sveikasis skaičius, ).

Pradiniuose duomenyse tarp raidės ir po jos esančio skaičiaus bei tarp dviejų skaičių palikta po vieną tarpą.

Pavyzdžiai

Jei aprašoma kryžkelė, kurios numeris 3, o į ją ateinama iš 5–os kryžkelės, tai eilutė atrodys: K 5 3 Jei aprašomas įėjimas į labirintą, kuriam suteiktas numeris 4, tai eilutė bus: K 0 4 Jei į aklavietę ateinama iš kryžkelės kurios numeris 2, o aklavietėje paslėpto brangakmenio vertė 4, tai eilutė bus: A 2 4

Rezultatai

Rezultatą - vienintelį skaičių - programa turi išvesti į rezultatų failą.

Pavyzdžiai

Pradiniai duomenys	Rezultatai	Paveikslas, iliustruojantis pavyzdį
8 9 K 10 9 K 4 7 A 9 5 K 5 3 A 3 3 A 1 8 K 0 4 A 2 4 K 4 5 K 4 10 A 1 7 A 3 2 K 7 1 A 3 4 A 9 8 K 10 2 A 7 5	5