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 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 ( 18 ) 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
hide comments
adarsh_raj:
20201223 07:28:54
Can this be solved using graph coloring?


scriptkiddiec:
20200903 09:38:02
suppose money contributed by 1 and 3 respectively are 8 and 9.


conprauser20:
20200708 17:26:20
Something might be wrong with the input, with Kotlin i got NZEC, though with C the same solution got accepted.. 

dante_part_2:
20200515 08:54:53
Nice problem Last edit: 20200515 08:55:30 

the_pythor:
20200512 13:56:02
Easy solution as the given constraints are very less. Just generated all the possibilities using recursion. We can do the same thing using Bitmask. 

satya1998:
20200501 19:28:46
Using bitmasking. Last edit: 20200501 19:53:22 

nadstratosfer:
20200206 23:06:24
mostafiz_53: Optimal selection is 2 (even though that means neither 1 nor 3 can go), 5 (this eliminates 4), 6 (no conflicts with anyone) and 9. 14+3+4+9 = 30.


mostafiz_53:
20200206 16:16:26
Can someone explain this output?


sandeepd:
20200109 21:51:21
All I can say is  thanks for this problem. Thanks a lot. 

amanharitsh:
20191027 10:23:08
AC in one go! Bitmasking :) 
Added by:  Alcatraz 
Date:  20161208 
Time limit:  0.100s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 
Resource:  Own Problem 