- Time limit: 1.00 s
- Memory limit: 128 MB
Pelaat peliä, jossa on huonetta ja 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 ja : huoneiden ja käytävien määrä. Huoneet on numeroitu .
Seuraavalla rivillä on kokonaislukua : kolikoiden määrä kussakin huoneessa.
Lopuksi syötteessä on riviä, jotka kuvaavat käytävät. Jokaisella rivillä on kaksi kokonaislukua ja : huoneesta on käytävä huoneeseen . Kaikki käytävät ovat yksisuuntaisia.
Tuloste
Tulosta yksi kokonaisluku: suurin mahdollinen kolikoiden määrä.
Rajat
Esimerkki
Syöte:
4 4 4 5 2 7 1 2 2 1 1 3 2 4
Tuloste:
16