Jako członek ICPC (Ibaraki Committee of Physical Competitions) odpowiadasz za zaplanowanie trasy maratonu w mieście Tsukuba. Oczekuje się wielu biegaczy, od początkujących po ekspertów.

Masz mapę miasta z wszystkimi odcinkami ulic odpowiednimi dla zawodów oraz wszystkimi ich skrzyżowaniami. Start znajduje się na skrzyżowaniu przed Tsukuba High, a meta na skrzyżowaniu przed City Hall. Oba są zaznaczone na mapie.

Aby uniknąć tłoku i zamieszania wśród biegaczy o różnych umiejętnościach, trasa nie może odwiedzać tego samego skrzyżowania dwukrotnie. Zatem choć odcinki ulic można pokonywać w obu kierunkach, każdy może wystąpić w trasie najwyżej raz. Głównym celem wydarzenia jest rekreacja i poprawa zdrowia mieszkańców, więc wyniki czasowe nie są ważne, a długość trasy można wybrać dowolnie.

Na każdym skrzyżowaniu trasy trzeba rozmieścić pewną liczbę pracowników. Sąsiednie skrzyżowania, czyli połączone bezpośrednio odcinkiem ulicy ze skrzyżowaniami trasy, również wymagają obsady, aby zwykły ruch nie zakłócał biegu. Dla danego skrzyżowania wymagana liczba pracowników jest taka sama, gdy leży ono na trasie i gdy sąsiaduje z trasą. Jednak różne skrzyżowania wymagają różnych liczb zależnie od wielkości i kształtu; liczby te także zaznaczono na mapie.

Władze miejskie chcą zmniejszyć koszty takich imprez, w tym koszty personelu. Napisz program planujący trasę wymagającą najmniejszej możliwej liczby pracowników i wypisujący tę liczbę.

Wejście

Wejście składa się z jednego testu przedstawiającego uproszczoną mapę miasta w następującym formacie.

n m
c1
...
cn
i1 j1
...
im jm

Pierwszy wiersz zawiera dwie dodatnie liczby całkowite $n$ i $m$. $n$ oznacza liczbę skrzyżowań na mapie ($2 \le n \le 40$), a $m$ liczbę odcinków ulic łączących sąsiednie skrzyżowania. Skrzyżowania są oznaczone liczbami od $1$ do $n$.

Następne $n$ wierszy podaje wymagane liczby pracowników. Liczba całkowita $c_k$ ($1 \le c_k \le 100$) w $k$-tym z tych wierszy jest liczbą pracowników wymaganą na skrzyżowaniu $k$.

Pozostałe $m$ wierszy podaje odcinki ulic między skrzyżowaniami. Każdy zawiera dwie liczby całkowite $i_k$ i $j_k$, oznaczające odcinek łączący skrzyżowania $i_k$ i $j_k$ ($i_k \ne j_k$). Każdą parę skrzyżowań łączy najwyżej jeden odcinek.

Bieg zaczyna się na skrzyżowaniu $1$, a meta jest na skrzyżowaniu $n$. Zagwarantowano istnienie co najmniej jednej trasy łączącej start z metą.

Wyjście

Wypisz liczbę całkowitą oznaczającą najmniejszą możliwą liczbę wymaganych pracowników.

Rysunek I.1. Trasa o najmniejszym koszcie dla przykładowego wejścia 1

Rysunek I.1 przedstawia trasę o najmniejszym koszcie dla przykładowego wejścia 1. Strzałki wskazują trasę, a szare koła oznaczają skrzyżowania wymagające obsady. Najmniejsza liczba wymaganych pracowników wynosi tu $17$.

Przykład

Wejście 1

6 6
3
1
9
4
3
6
1 2
1 4
2 6
5 4
6 5
3 2

Wyjście 1

17