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

hide comments
abexcorp: 2024-01-25 23:57:46

SIGABRT in C#, same program in C++ passes without issues.

meatcode: 2022-10-04 06:17:47

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

Output:
30

so it's been decided that out of two conflicted person only one of them will join, hence choose the one one which
provides more money if 2 is contributing 5 and 3 is 10 then 3 will go and if 3 is contributing 10 and 4 is 12 then 4
will be going.

joe201810a: 2021-12-12 23:27:14

no comment

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.


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