RDRUG - Rage Drug

no tags 

Dr. Banner (a.k.a. The Hulk) is synthesizing a drug that will help him control his rage. There are a total of N atoms of various atomic masses.

Banner knows that to create a bond between two atoms the energy required is equal to the sum of the atomic masses of the two atoms.

Currently some of the atoms are connected to one another forming compounds.

Banner wants to join all separate atoms and compounds into a single compound by creating chemical bonds. Each atom can form at max one more bond. Help Dr. Banner to find out the minimum energy required to synthesize his drug.

INPUT

Input starts with an integer T, the number of test cases. Each test case starts with a line containing integers N, M denoting the number of atoms and the number of bonds already formed respectively. M lines contain 2 integers i and j denoting a chemical bond between the ith and the jth atom. The next N lines contains one integer each where the integer on ith line denotes the atomic mass of the ith atom.

OUTPUT

Print T lines, where the ith line is the answer to the ith test case. If it is not possible to link the atoms print -1;

PS: If you mislead Dr. Banner, he might lose his temper and SMASH you to bits.

CONSTRAINTS

1 <= T <= 12
1 <= N <= 100000
1 <= AtomicMass <= 10000
0 <= M <= 10^6 (1000000)
1 <= i, j <= N

Sample Input:

2
6 6
1 2
2 3
1 3
4 5
5 6
4 6
1
3
5
2
4
6
4 0
1
2
3
4

Sample Output:

3
-1

hide comments
anonymous: 2016-03-30 15:57:32

Note: Constraints say that there is at least one bond (M >= 1), but in the
second sample test case there are no bonds at all.
[Simes]: Fixed

Last edit: 2023-09-09 17:27:48
Alex Anderson: 2013-02-21 04:01:52

I agree, it made me think quite a bit and used some nice math.

Last edit: 2013-02-21 04:02:49
Ehor Nechiporenko: 2013-02-19 20:17:40

Amazing problem. CodeCraft contest is realy cool!


Added by:smit hinsu
Date:2013-02-18
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeCraft 13 , Author : Jay Pandya