Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Kolikot

Kolikot


View task | Model solution | Statistics


Kolikot

Time limit:1.00 s
Memory limit:128 MB

Pelaat peliä, jossa on $n$ huonetta ja $m$ käytävää niiden välillä. Jokaisessa huoneessa on tietty määrä kolikoita. Montako kolikkoa voit kerätä korkeintaan, kun saat päättää itse, mistä huoneesta aloitat ja mihin huoneeseen lopetat?

Syöte

Syötteen alussa on kaksi kokonaislukua $n$ ja $m$: huoneiden määrä ja käytävien määrä. Huoneet on numeroitu $1,2,\ldots,n$.

Sitten syötteessä on $n$ kokonaislukua $k_1,k_2,\ldots,k_n$: kolikoiden määrä kussakin huoneessa.

Lopuksi syötteessä on $m$ riviä, jotka kuvaavat käytävät. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$. Tämä tarkoittaa, että huoneesta $a$ on käytävä huoneeseen $b$. Kaikki käytävät ovat yksisuuntaisia.

Tuloste

Tulosta yksi kokonaisluku: montako kolikkoa voit kerätä enintään.

Rajat
Esimerkki

Syöte:
4 4
4 5 2 7
1 2
2 1
1 3
2 4


Tuloste:
16