Problem Description

An NGO wants to arrange the funds for flood relief. It has divided volunteers into groups. A volunteer can only be a part of single group. Your task is to find the maximum funds collected by the group.

Constraints

0 < N, P <= 10000

0 < A, B <= N

Input

First line contains one integer N, denoting number of volunteers.

Second line contains N space separated integers, representing the amount collected by each volunteer. The index of integer is the volunteer starting from 1.

Third line contains the number od=f pairs, p.

Next P lines contain two space separated integers, A and b where A represents the first person and b represents the second person in the pairs, P.

Output

One line containing an integer, representing the maximum funds collected by the group.

Time Limit

2 s

Examples

Example 1

Input

5

23 43 123 54 2

3

1 3

2 3

1 2

Output

189

Explanation

In the above example, we have five volunteer [1,2,3,4,5] who have collected [23,43,123,54,2] respectively.

We have three groups that consists of [1,2,3],[4],[5]. First group collects 189 units of money, second group collects 54 units of money and third group collects 2 units of money. The maximum funds collected by any group is 189. Hence the output is 189.