#P1379. [Baltic2001]Postman

[Baltic2001]Postman

题目描述

邮局位于 11 号村庄。邮递员需要从村庄 11 出发并回到村庄 11,至少经过每个村庄和每条道路一次。道路为无向边,可以有重边和自环。保证所有村庄连通,且每个村庄的度数为 22、44 或 88(自环对度数贡献 22)。

第 ii 个村庄有期望值 WiW_i。若它是路线中第 kk 个首次到访的村庄,村庄向邮局支付 Wi−kW_i-k 元;此值为负时,表示邮局支付其相反数。邮局每经过一条道路向邮递员支付 11 元,重复经过也需再次支付。

求使邮局总收益最大的路线长度,即所经过道路的总次数。本题仅输出该长度。

输入格式

第一行两个整数 N,MN,M,表示村庄数和道路数,1≤N≤2001\le N\le200。 接下来 NN 行,每行一个整数 WiW_i,1≤Wi≤10001\le W_i\le1000。 接下来 MM 行,每行两个整数,表示道路两端的村庄编号。

输出格式

输出邮局收益最大时的路线长度。

样例输入

6 7
1
7
4
10
20
5
2 4
1 5
2 1
4 5
3 6
1 6
1 3

样例输出

7