Piet Hein 是一位荷兰海军军官，活跃于荷兰联省共和国与西班牙之间的八十年战争期间。他最著名的胜利是 1628 年在古巴附近俘获了“银舰队”（Zilvervloot），当时他拦截了多艘从美洲西班牙殖民地向西班牙运送白银的西班牙船只。关于这场著名海战的细节较为模糊，因此下文的描述可能包含一些历史上的不准确之处。

银舰队由装载银币的船只组成。Piet Hein 的基本策略很简单：从舰队中拖走若干船只，以夺取其中的财物。

为了阻止荷兰人实施这一计划，西班牙人使用巨大的铁链将舰队中的所有船只连接在一起。舰队中的每艘船都至少固定在另一艘船上；任意两艘船之间最多由一条链子连接；并且西班牙人确保链子之间不会交叉，否则它们可能会缠绕成结。最终，船只和连接它们的链子构成了一个连通的平面图。

然而，西班牙人的预防措施反而使情况变得更糟。作为一名经验丰富的海军军官，Piet Hein 知道，如果一个群体中的每两艘船之间都由链子直接相连，那么拖走这组船只就最容易。他将这样的群体称为“链组”（chaingroups）。

Piet Hein 命令他的部下在用几发精准的炮弹切断与西班牙舰队其余船只的连接后，拖走包含最大财物的链组中的所有船只。一个链组的总财物是构成该链组的船只中银币数量的总和。

图 1 – 以图论形式表示的银舰队：每个点表示舰队中的一艘船，每条线表示连接两艘船的链子。图中由虚线连接的船只对应于提供最高银币总价值的链组。在这种情况下，Piet Hein 从舰队中掠夺了 4500 枚银币。

任务

给定银舰队的描述，找出拥有最高财物价值的链组的价值（即构成该链组的船只中银币的总数）。

输入格式

对于每个测试用例：

• 一行包含两个整数 $v$ ($2 \le v \le 450$) 和 $e$ ($1 \le e \le 900$)，分别表示舰队中船只的数量和链子的数量。
• 接下来 $v$ 行，指定 $S_1, S_2, \dots, S_v$，即第 $i$ 艘船携带的银币数量 ($1 \le i \le v$)。$S_i$ 为正整数，且 $100 \le S_i \le 6000$。
• 接下来，对于每条链子，一行包含两个整数 $c_{start}$ 和 $c_{end}$，表示由该链子连接的两艘船，其中 ($1 \le c_{start} < c_{end} \le v$)。

每个舰队构成一个连通的平面图。

输出格式

对于每个测试用例，输出一行，包含一个正整数：Piet Hein 的舰队所俘获的银币数量。

样例

输入 1

4 6
100
5000
1000
2000
1 2
1 3
1 4
2 3
2 4
3 4
6 8
1500
1000
100
2000
500
300
1 2
1 3
1 4
2 4
3 5
4 5
4 6
5 6

输出 1

8100
4500