시골 우체부

시골 우체부는 마을에 사는 사람들과 마을을 잇는 도로변에 사는 사람들, 즉 지역의 모든 주민에게 우편물을 배달해야 한다.

우체부가 모든 도로를 지나고 모든 마을을 적어도 한 번씩 방문하는 경로를 정하도록 도와주자. 여기서 다루는 모든 경우에는 그런 경로가 반드시 존재한다. 어떤 경로를 택하느냐에 따라 우체국이 받는 금액이 달라지므로 경로마다 가치가 다를 수 있으며, 중요한 것은 우체부가 아니라 우체국의 이익이다.

각 마을은 우체부가 되도록 일찍 도착하기를 바라기 때문에 우체국과 다음과 같은 계약을 맺는다. 마을 $i$가 우체부가 방문한 서로 다른 마을 중 $k$번째라고 하자. 즉, 우체부가 마을 $i$에 처음 도착하기 전에 이미 서로 다른 마을 $k-1$개를 방문했다는 뜻이다. 만약 $k \le w(i)$이면 마을이 우체국에 $w(i) - k$ 유로를 지불하고, $k > w(i)$이면 우체국이 마을에 $k - w(i)$ 유로를 지불한다. 여기에 더해, 우체국은 경로에서 연속한 두 마을 사이를 이동할 때마다 우체부에게 1유로를 지불한다.

마을은 $n$개이며 $1$번부터 $n$번까지 번호가 매겨져 있다. 우체국은 $1$번 마을에 있으므로 경로는 반드시 $1$번 마을에서 시작한다. 각 마을에서는 정확히 $2$개, $4$개 또는 $8$개의 도로가 만난다. 두 마을을 잇는 도로가 여러 개 있을 수도 있고, 한 마을에서 나와 같은 마을로 돌아오는 도로가 있을 수도 있다.

모든 유효한 경로 중에서 우체국이 얻을 수 있는 최대 총이익을 유로 단위로 구하여라. 만약 어떤 경로를 택해도 우체국이 손해를 본다면, 손해가 가장 적은 경우를 음수로 출력한다.

첫째 줄에 두 정수 $n$과 $m$이 공백 하나로 구분되어 주어진다. $n$은 마을의 수($1 \le n \le 200$), $m$은 도로의 수이다.

다음 $n$개의 줄에는 각각 양의 정수가 하나씩 주어진다. $i+1$번째 줄의 값은 $w(i)$($1 \le w(i) \le 1000$)로, 마을 $i$가 우체국에 지불하는 기본 금액이다(위 계약에 따라 조정된다).

그다음 $m$개의 줄에는 각각 두 정수가 공백 하나로 구분되어 주어지며, 해당 도로가 잇는 두 마을의 번호를 나타낸다.

우체국이 얻을 수 있는 최대 총이익을 유로 단위 정수 하나로 출력한다. 이 값은 음수일 수 있다.