Coin Collector.

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Rust, Scala, ~~Swift~~, VB, Zig

Un juego tiene $n$ ~n~ habitaciones y $m$ ~m~ túneles entre ellas. Cada habitación tiene un número determinado de monedas. ¿Cuál es el número máximo de monedas que puedes recoger mientras te mueves por los túneles cuando puedes elegir libremente tu habitación inicial y final?

Entrada

La primera línea de entrada tiene dos números enteros $n$ ~n~ y $m$ ~m~: el número de habitaciones y de túneles. Las habitaciones se numeran $1,2,\ldots,n$ ~1,2,\ldots,n~. Luego, hay $n$ ~n~ enteros $k_1,k_2,\ldots,k_n$ ~k_1,k_2,\ldots,k_n~: el número de monedas en cada habitación. Por último, hay $m$ ~m~ líneas que describen los túneles. Cada línea tiene dos enteros $a$ ~a~ y $b$ ~b~: hay un túnel de la habitación $a$ ~a~ a la habitación $b$ ~b~. Cada túnel es un túnel unidireccional.