CSES - Kolikot
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Pelaat peliä, jossa on nn huonetta ja mm käytävää. Jokaisessa huoneessa on tietty määrä kolikoita. Montako kolikkoa voit kerätä enintään, kun saat päättää vapaasti, mistä huoneesta aloitat ja mihin huoneeseen lopetat?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja mm: huoneiden ja käytävien määrä. Huoneet on numeroitu 1,2,,n1,2,\dots,n.

Seuraavalla rivillä on nn kokonaislukua k1,k2,,knk_1,k_2,\dots,k_n: kolikoiden määrä kussakin huoneessa.

Lopuksi syötteessä on nn riviä, jotka kuvaavat käytävät. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: huoneesta aa on käytävä huoneeseen bb. Kaikki käytävät ovat yksisuuntaisia.

Tuloste

Tulosta yksi kokonaisluku: suurin mahdollinen kolikoiden määrä.

Rajat

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1ki1091 \le k_i \le 10^9
  • 1a,bn1 \le a,b \le n

Esimerkki

Syöte:

4 4
4 5 2 7
1 2
2 1
1 3
2 4

Tuloste:

16