ICPC (Ibaraki Committee of Physical Competitions) の一員として、Tsukuba 市で行われるマラソン大会の経路を計画する担当になりました。初心者から熟練者まで、大勢のランナーが参加する予定です。

大会に適したすべての道路区間と、その上のすべての交差点を記した市街地図があります。レースは Tsukuba High の前の交差点から始まり、City Hall の前の交差点がゴールです。両方とも地図に示されています。

技能の異なるランナーの混雑と混乱を避けるため、経路は同じ交差点を 2 回訪れてはいけません。したがって、道路区間はどちらの向きにも使えますが、経路に含められるのは最大 1 回です。大会の主な目的は市民のレクリエーションと健康増進なので、タイムは重要ではなく、経路の距離は自由に決められます。

経路上のすべての交差点には、一定数の係員を配置する必要があります。それらに隣接する交差点、つまり経路上の交差点と 1 本の道路区間で直接つながる交差点にも、一般の交通がレースを妨げないよう係員を配置する必要があります。ある交差点が経路上にある場合と経路に隣接する場合とで必要な人数は同じですが、交差点ごとに大きさや形状によって人数は異なり、その人数も地図に示されています。

市当局は、このような大会の人件費を含む費用を減らしたいと考えています。必要な係員の人数が最小になる経路を計画し、その人数を出力するプログラムを作成してください。

入力

入力は、簡略化した市街地図を表す 1 つのテストケースで、次の形式です。

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

最初の行には 2 つの正の整数 $n$ と $m$ が与えられます。$n$ は地図上の交差点数（$2 \le n \le 40$）、$m$ は隣接する交差点を結ぶ道路区間数です。交差点は $1$ から $n$ の整数で識別されます。

続く $n$ 行は必要な係員の人数を示します。その $k$ 行目の整数 $c_k$（$1 \le c_k \le 100$）は、交差点 $k$ に必要な人数です。

残りの $m$ 行は、交差点間の道路区間を列挙します。各行には、交差点 $i_k$ と $j_k$ を結ぶ区間を表す 2 つの整数 $i_k$、$j_k$（$i_k \ne j_k$）が与えられます。同じ交差点の組を結ぶ道路区間は最大 1 本です。

レースは交差点 $1$ で始まり、交差点 $n$ がゴールです。スタートとゴールを結ぶ経路が少なくとも 1 つあることは保証されています。

出力

必要な係員の人数の最小値を表す整数を出力してください。

図 I.1．入力例 1 の最小費用の経路

図 I.1 は入力例 1 の最小費用の経路を示します。矢印は経路を表し、灰色の円は係員の配置が必要な交差点です。この場合、必要な最小人数は $17$ です。

入出力例

入力 1

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

出力 1

17