CSES - Lentoasema
  • 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 nn ja mm: tarkastuspisteiden määrä ja käytävien määrä. Tarkastuspisteet on numeroitu 1,2,,n1,2,\ldots,n. Tarkastuspiste 1 on lähtöaula ja tarkastuspiste nn on porttialue.

Seuraavalla rivillä on nn kokonaislukua r1,r2,,rnr_1,r_2,\ldots,r_n: montako matkustajaa voi kulkea tarkastuspisteen kautta minuutissa. Määrä 1-1 tarkoittaa, että rajoitusta ei ole. Lähtöaulassa ja porttialueella ei ole koskaan rajoitusta.

Lopuksi syötteessä on mm riviä, joista jokainen kuvaa yhden käytävän. Kullakin rivillä on kaksi kokonaislukua aa ja bb: 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

  • 2n1002 \le n \le 100
  • 1m10001 \le m \le 1000
  • 1ri109-1 \le r_i \le 10^9
  • 1a,bn1 \le a, b \le n

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