So, it was winter and Me and 8 of my friends decided to plan a trip to GOA. Since the Bars and Clubs are too Expensive out there, we decided to pool money together for our whole trip expenses. Now since every group has some internal politics going on, same applies to our group also :P. 2 Members that are having a cold war between them won't go to the trip if the other one is going. But Since we want to enjoy a lavish party, we want to maximize the pooled money. So, for this task I've chosen my marwari friend Mohit to solve this problem (He's good at money matters). Your task is to help Mohit achieve the maximum pooled money.

Input

First Line will contain 8 space separated integers denoting the money contributed by each member in order.

The next line will contain the total number of pairs having a cold war in between them. Let us denote this by P.

The next P lines will contain 2 numbers separated by a space showing the members having a cold war. Numbers used to denote members will be (1 - 8) for each of the 8 members.

Constraints

Everything is guaranteed to easily fit in 32 bit integer type.

Output

Output will give the maximum amount of money that can be pooled.

Example

Input:
3 14 5 2 3 4 1 9
4
1 2
2 3
4 5
7 8

Output:
30