So , it was winter and Me and 8 of my friends decided to plan a trip to GOA . Since the Bars ans 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 aplies 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 seperated 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 seperated by a space showing the members having a cold war  . Numbers used to denote members will be ( 1-8 ) for each 8 members .

Constraints:

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

Output description

Output will give the maximum amt 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