Battle for Silver

Piet Hein was a Dutch naval officer during the Eighty Years' War between the United Provinces of the Netherlands and Spain. His most famous victory was the capture of the Zilvervloot (the Silver Fleet) near Cuba in 1628, when he intercepted Spanish vessels that were carrying silver from the Spanish colonies in the Americas back to Spain. Records of the battle are sketchy, so the description below may contain historical inaccuracies.

The Silver Fleet consisted of vessels loaded with silver coins. Piet Hein's plan was simple. He towed away some of the vessels and kept what they carried.

To stop the Dutch, the Spanish tied every ship in the fleet together with heavy iron chains. Each vessel was fixed to at least one other vessel, any two vessels were connected by at most one chain, and the Spanish kept the chains from crossing so that they could not tangle into a knot. The vessels and the chains therefore form a connected planar graph.

The precaution only made things worse for the Spanish. Piet Hein knew from experience that a group of ships is easiest to tow when every two ships in the group are joined by a chain. He called such a group a chaingroup.

Piet Hein picked the chaingroup holding the most booty, cut the chains that linked it to the rest of the Spanish fleet with a few accurate cannon shots, and ordered his men to tow away every ship in it. The booty of a chaingroup is the total number of silver coins on the vessels that make it up.

Draw the fleet as a graph: one dot is one vessel, and one line is one chain between two vessels. Given a description of the Silver Fleet, find the booty of the chaingroup with the highest number of silver coins.

The input holds several test cases and continues until the end of the file. Each test case has this format.

• One line with two integers $v$ ($2 \le v \le 450$) and $e$ ($1 \le e \le 900$), the number of vessels in the fleet and the number of chains.
• Then $v$ lines with $S_1, S_2, \dots, S_v$, one per line. $S_i$ is the number of silver coins carried by vessel $i$, a positive integer with $100 \le S_i \le 6000$.
• Then $e$ lines, one per chain, each with two integers $c_{start}$ and $c_{end}$, the two vessels that the chain connects, where $1 \le c_{start} < c_{end} \le v$.

Every fleet forms a connected planar graph.

For each test case, print one line with a single positive integer, the number of silver coins that Piet Hein captures.