Matcom Online Grader

Los estudiantes de las escuelas de Cuba se reúnen todos los años en  invierno en un campamento para realizar  la tradicional búsqueda de los tesoros escondidos en las cuevas. A cada competidor  se  le entrega un mapa  (representado  por un grafo orientado) con  todas las  cuevas  de  la  región  donde  se  encuentran  los  tesoros  y  los  caminos  que  existen  entre ellas.  Cada  cueva  tiene  un  tesoro  el  cual  tiene  un  determinado  valor  que  el  competidor obtiene  si pasa  por  ese  lugar.   Es posible  que  no  se pueda  ir  a todas  las cuevas, pues  en ocasiones los caminos son de difícil acceso. Si usted visita una cueva más de una vez solo recibe el beneficio de los valores de los tesoros la primera vez que pasó por ese lugar. Por lo tanto, el competidor debe seguir una ruta que parta del campamento hasta el destino final  y debe pasar por  las  cuevas  para  recoger  los  tesoros  obteniendo  la suma máxima    de  todos sus valores.

Tarea

Hacer un programa que permita:

-  Leer la cantidad  de cuevas,  el  valor que tienen los tesoros en cada cueva y los caminos que existen entre las cuevas.
-  Determinar  cuál  es  la suma  máxima de los valores  de los tesoros que  puede alcanzar  un competidor al seleccionar su ruta  óptima.
-  Escribir el valor máximo determinado.

Input

La entrada contiene:

Línea  1: $N$  y  $M$,  separados  entre  sí  por  un  espacio  en  blanco,  los  cuales  representan  el número de cuevas y la cantidad de caminos orientados entre ellas.

Línea 2: $P_0, P_1, ..., P_{N-1}$, separados entre sí por un espacio en blanco, los cuales representan los  valores  de  los  tesoros  en  cada cueva.  El  campamento,  punto  inicial    de  la  ruta  tiene el número $0$ y el final tendrá el número $N - 1$.

Línea 3...M + 2: $n_1$ y $n_2$, separados entre sí por un espacio en blanco,  los cuales representan un camino orientado de la cueva $n_1$  a la cueva $n_2$.

Restricciones

-  $2 \leq N \leq 10000$
-  $1 \leq M \leq 100000$
-  $0 \leq P_i \leq 10000$

Output

La salida contiene en una línea  la suma máxima de los valores de los tesoros que puede obtener un competidor al seleccionar su ruta  óptima.

Sample test(s)

Hints

El  mayor  valor  de  la  suma  de  los  tesoros  se  obtuvo  al  hacer  el  recorrido  a  través  de  las siguientes cuevas:  $0 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 5$, dando un valor total de $12 + 2 + 7 + 8 + 0 + 13 = 42$.