Como miembro de ICPC (Ibaraki Committee of Physical Competitions), eres responsable de planificar la ruta de un maratón en la ciudad de Tsukuba. Se espera una gran cantidad de corredores, desde principiantes hasta expertos.
Dispones de un mapa con todos los tramos de calle adecuados para el evento y todos sus cruces. La carrera empieza en el cruce frente a Tsukuba High y termina en el cruce frente a City Hall; ambos están marcados en el mapa.
Para evitar aglomeraciones y confusión entre corredores de distintas habilidades, la ruta no debe visitar un mismo cruce dos veces. Por tanto, aunque los tramos pueden recorrerse en ambos sentidos, cada uno puede incluirse en la ruta como máximo una vez. Como el objetivo principal es la recreación y la mejora de la salud de los ciudadanos, los tiempos no son importantes y la distancia puede elegirse libremente.
Debe situarse cierta cantidad de personal en cada cruce de la ruta. Los cruces adyacentes, es decir, conectados directamente por un tramo de calle con los cruces de la ruta, también necesitan personal para impedir que el tráfico ordinario interfiera con la carrera. Un cruce requiere la misma cantidad de personal cuando está en la ruta que cuando es adyacente a ella, pero cruces diferentes requieren cantidades distintas según su tamaño y forma, también indicadas en el mapa.
Las autoridades municipales desean reducir los costes de estos eventos, incluidos los de personal. Tu tarea es escribir un programa que planifique una ruta con la mínima cantidad posible de personal necesario e imprima esa cantidad.
Entrada
La entrada consiste en un único caso de prueba que representa un mapa resumido de la ciudad, con el siguiente formato.
n m c1 ... cn i1 j1 ... im jm
La primera línea contiene dos enteros positivos $n$ y $m$. $n$ indica la cantidad de cruces del mapa ($2 \le n \le 40$) y $m$ la cantidad de tramos de calle que conectan cruces adyacentes. Los cruces se identifican con enteros de $1$ a $n$.
A continuación hay $n$ líneas con las cantidades de personal necesarias. El entero $c_k$ ($1 \le c_k \le 100$) de la línea $k$ es la cantidad de personal necesaria para el cruce $k$.
Las $m$ líneas restantes enumeran los tramos entre cruces. Cada una contiene dos enteros $i_k$ y $j_k$ que representan un tramo entre los cruces $i_k$ y $j_k$ ($i_k \ne j_k$). Hay como máximo un tramo que conecte el mismo par de cruces.
La carrera empieza en el cruce $1$ y termina en el cruce $n$. Se garantiza que existe al menos una ruta entre el inicio y la meta.
Salida
Imprime un entero que indique la mínima cantidad posible de personal necesario.
Figura I.1. La ruta de menor coste para la entrada de ejemplo 1
La figura I.1 muestra la ruta de menor coste para la entrada de ejemplo 1. Las flechas indican la ruta y los círculos grises son cruces que necesitan personal. La cantidad mínima de personal necesaria en este caso es $17$.
Ejemplos
Entrada 1
6 6 3 1 9 4 3 6 1 2 1 4 2 6 5 4 6 5 3 2
Salida 1
17