The Rural Postman

A rural postman must deliver mail to everyone in the region: the people living in the villages and those living along the roads that connect the villages.

Help him choose a route that drives along every road and visits every village at least once. In every case considered here, such a route is guaranteed to exist. Routes can differ in value, because the post office is paid differently depending on which route is taken, and it is the post office's profit (not the postman's) that matters.

Each village wants the postman to arrive as early as possible, so every village signs the following contract with the post office. Suppose village $i$ is the $k$-th distinct village the postman reaches, meaning he had already visited $k-1$ different villages before reaching village $i$ for the first time. If $k \le w(i)$, the village pays the post office $w(i) - k$ euros. If $k > w(i)$, the post office pays the village $k - w(i)$ euros. On top of that, the post office pays the postman one euro for every drive between two consecutive villages on the route.

There are $n$ villages, numbered $1$ to $n$. The post office is in village $1$, so the route must start in village $1$. Exactly $2$, $4$, or $8$ roads meet at each village. Two villages may be connected by several different roads, and a road may also return to the village it starts from.

Compute the maximum total profit, in euros, that the post office can achieve over all valid routes. If every route makes the post office lose money, report the smallest possible loss as a negative number.

The first line contains two integers $n$ and $m$ separated by a single space: the number of villages $n$ ($1 \le n \le 200$) and the number of roads $m$.

Each of the next $n$ lines contains one positive integer. The value on line $i+1$ is $w(i)$ ($1 \le w(i) \le 1000$), the base amount village $i$ would pay the post office (adjusted by the contract described above).

Each of the next $m$ lines contains two integers separated by a single space: the numbers of the two villages joined by that road.

Print one integer: the maximum total profit, in euros, that the post office can obtain. The value may be negative.