ALCATRAZ2 - GO GOA GONE

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

Added by:Alcatraz
Date:2016-12-08
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Own Problem

hide comments
2017-09-27 05:04:06
Take care of p=0.
2017-07-04 14:30:11
simple bitmasking!!
nothing else
2017-06-11 13:51:48
AC in one GO !!! used simple recursive !!!
2017-05-02 06:32:59 shahzada
no need of dp ....simple recursion passed in 0.00s
2017-04-11 20:23:25
dp+bitmasking ....sahi pallav :)
2017-02-24 04:36:40
DP is about 5 times faster than brute force

Last edit: 2017-02-25 00:03:06
2017-02-23 22:24:02
DP + bitmasking
2017-02-11 15:42:40
Code is perfectly running in my ide but not in SPOJ why?
2017-01-22 19:31:54
dp + bitmasking :)
2017-01-22 17:09:17
AC in 1 go simple one..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.