Electric Power Grid

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Grid Computing is a hot topic these years. Many people have heard of it, but some are still confused about it. In fact, this concept came from the electric power grid. Within an electric power grid, power stations and power users are all connected to the grids. Power stations generate the electricity and input it into the grid. On the other hand, the users get electricity from the grid, unaware where it comes from. Grid Computing works in the similar way.

Electric power grids worked very well in the past one hundred years. Recently, a plan about building a new electric power grid in our province was being discussed by GDCPC(Guangdong Construction Power Committee). This grid will conver all the cities and supply the maximum electric power. The electric network has been constructed. The committee members are now discussing where the power stations should be located. This grid has the following features:
 
(1) All cities are within the network.
(2) There is at most one power station built within a city. Of course, it locates far away from residential area.
(3) There is at most one connection between two cities.
(4) There may be some circles in the network, none of which contains more than three distinct cities. For example, the network in Figure 1 is allowed while the one in Figure 2 is not. 


(5) Taking safety into consideration, if two cities are directly connected, they cannot both have power stations.
(6) Due to the enviroment condition of the cities, the output of each power station cannot exceed a limitatin value. These values differ from city to city. In order to provide the maximum electric power, the location of the power stations should be carefully selected. Now, it is your task to help the committee decide the cities in which power stations will be built.

Input

There are multiple cases.
 
The input format for each case is: The first line contains only one integer N (1<=N<=100) indicating the number of the city. There are N positive integers (not greater than 1000) in the second line. The ith integer is the limitation value of the ith city. And then there's a number in a line indicating the number of edges,i.e., the number of pairs of linked cities. The following lines will describe the structure of the network. Each line contains two integers k and m, indicating that the kth city and the mth city is directly connected. N=0 indicates the end of input.

Output

For each case output one line containing one integer. It is the maximum electric power that the grid will provide.

Sample Input

2
1 2
1
1 2
5
1 2 3 4 5
6
1 2
2 3
1 3
3 4
3 5
4 5
0

Sample Output

2
7

Hint

Source

ZSUCPC