- Time limit: 1.00 s
- Memory limit: 128 MB
Sinulle on annettu tiedot lentoaseman rakenteesta ja tehtäväsi on laskea, millä nopeudella matkustajia voi kulkea lähtöaulasta porttialueelle.
Lentoasema muodostuu käytävistä ja tarkastuspisteistä (turvatarkastus, passintarkastus, jne.). Jokaiseen tarkastuspisteeseen liittyy tieto, montako matkustajaa sen kautta voi kulkea minuutissa.
Jokaisen käytävän läpi voi kulkea rajattomasti matkustajia.
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua ja : tarkastuspisteiden määrä ja käytävien määrä. Tarkastuspisteet on numeroitu . Tarkastuspiste 1 on lähtöaula ja tarkastuspiste on porttialue.
Seuraavalla rivillä on kokonaislukua : montako matkustajaa voi kulkea tarkastuspisteen kautta minuutissa. Määrä tarkoittaa, että rajoitusta ei ole. Lähtöaulassa ja porttialueella ei ole koskaan rajoitusta.
Lopuksi syötteessä on riviä, joista jokainen kuvaa yhden käytävän. Kullakin rivillä on kaksi kokonaislukua ja : mistä pisteestä käytävä alkaa ja mihin se päättyy. Kaikki käytävät ovat yksisuuntaisia.
Tuloste
Ohjelmasi tulee tulostaa yksi kokonaisluku: suurin mahdollinen matkustajien läpivirtausnopeus lähtöaulasta porttialueelle.
Voit olettaa, että vastaus ei ole ääretön.
Rajat
Esimerkki
Syöte:
7 8 -1 40 50 10 -1 20 -1 1 2 1 3 3 4 3 5 2 6 4 7 5 7 6 7
Tuloste:
70