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 ( 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

hide comments
adarsh_raj: 2020-12-23 07:28:54

Can this be solved using graph coloring?

scriptkiddiec: 2020-09-03 09:38:02

suppose money contributed by 1 and 3 respectively are 8 and 9.
then in that case how to use recursion to solve the problem because we have to ignore 2 because if 2 doesnot go then 1 and 3 will go and the total money pooled by 1 and 3 will be 17. (which was 14 in case of 2). Someone please suggest an algorithm for this problem,I am in urgent need of it.

conprauser20: 2020-07-08 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: 2020-05-15 08:54:53

Nice problem

Last edit: 2020-05-15 08:55:30
the_pythor: 2020-05-12 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: 2020-05-01 19:28:46

Using bitmasking.

Last edit: 2020-05-01 19:53:22
nadstratosfer: 2020-02-06 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.

Amitayush Thakur: My Py3 solution doesn't use any defensive input techniques and got AC even despite a very unsafe thing for this type of algo that I wouldn't try nowadays.

mostafiz_53: 2020-02-06 16:16:26

Can someone explain this output?

sandeepd: 2020-01-09 21:51:21

All I can say is - thanks for this problem. Thanks a lot.

amanharitsh: 2019-10-27 10:23:08

AC in one go! Bitmasking :)


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