Los estudiantes de las escuelas de IslaGrande 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 desde la entrada 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 hacia la salida el valor máximo determinado.

Entrada

• Línea 1: ~N~ y ~M~, separados entre si 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 si 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 si por un espacio en blanco, los cuales representan un camino orientado de la cueva ~n_1~ a la cueva ~n_2~.

Salida

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

Restricciones

• ~2 \leq N \leq 10 000~.
• ~1 \leq M \leq 100 000~.
• ~0 \leq P_i \leq 10 000~.

Ejemplos de Entrada

6 7
12 11 2 7 8 13
0 1
1 5
0 2
2 5
2 3
3 4
4 2

Ejemplos de Salida

42

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

Concurso Nacional de Computación, Curso 2009-10. Día 2, Problema B.