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 (“Silver Fleet”) near Cuba in 1628, where he intercepted a number of Spanish vessels that were carrying silver from the Spanish colonies in the Americas to Spain. Details about this famous naval battle are sketchy, so the description below may contain some historical inaccuracies.

The Silver Fleet consisted of vessels containing silver coins. Piet Hein's basic strategy was simple: tow away a number of vessels from the fleet, in order to capture their contents.

In an attempt to prevent the Dutch from carrying out this plan, the Spanish tied all the ships in their fleet together using huge iron chains. Each vessel in their fleet was fixed to at least one other vessel; any two vessels were connected by at most one chain; and the Spanish made sure that the chains did not cross each other, otherwise they could get tied up into a knot. As an end result, the vessels and the chains connecting them formed a connected, planar graph.

However, the Spanish preventive measures only made their situation worse. As an experienced naval officer, Piet Hein knew that towing away a group of ships was easiest if, for every two ships in the group, the ships were connected by a chain. He called such groups chaingroups.

Piet Hein ordered his men to tow away all the ships in the chaingroup that contained the largest amount of booty, after severing the links with the remaining ships in the Spanish fleet with a few highly accurate canon shots. The total booty in a chaingroup is the total number of silver coins in the vessels that make up the chaingroup.

Figure 1: Illustration of second sample input. The Silver Fleet represented as a graph. Each dot denotes a vessel in the fleet, while each line denotes a chain that connects two vessels. The vessels that are connected in the figure by the dashed lines correspond to the chaingroup that provides the highest total value of silver coins. In this case, Piet Hein loots 4500 silver coins from the fleet.

Given a description of the Silver Fleet, find the value of the chaingroup with the highest amount of booty (i.e., total number of silver coins in the ships that make up the chaingroup).

Input Specification

Each test case is described by the following lines:

• A line containing two integers v (2 ≤ v ≤ 450) and e (1 ≤ e ≤ 900), the number of vessels in the fleet and the number of chains, respectively.
• Then, v lines specifying S₁, S₂, …, S_v, the amount of silver coins carried by vessel i (1 ≤ i ≤ v). The S_i will be positive integers, where 100 ≤ S_i ≤ 6000.
• Then, for each chain, a line containing two integers c_start and c_end, the two vessels connected by the chain (1 ≤ c_start < c_end ≤ v).

Each fleet forms a connected, planar graph.

Output Specification

For each test case, output one line containing a single positive integer: the number of silver coins that is captured by Piet Hein's fleet.

Sample Input

1. 4 6
2. 100
3. 5000
4. 1000
5. 2000
6. 1 2
7. 1 3
8. 1 4
9. 2 3
10. 2 4
11. 3 4
12. 6 8
13. 1500
14. 1000
15. 100
16. 2000
17. 500
18. 300
19. 1 2
20. 1 3
21. 1 4
22. 2 4
23. 3 5
24. 4 5
25. 4 6
26. 5 6

download as text file

Output for Sample Input

1. 8100
2. 4500

download as text file