Sinulle on annettu tieto 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 n ja m: tarkastuspisteiden määrä ja käytävien määrä. Tarkastuspisteet on numeroitu 1,2,\ldots,n. Tarkastuspiste 1 on lähtöaula ja tarkastuspiste n on porttialue.

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

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

• 1 \le n \le 50
• 1 \le m \le 100
• 1 \le r_i \le 10^9
• 1 \le a_i, b_i \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