Minister Golu Builds Roads

4.3

15 votes
Easy-Medium
Problem

King Kala the Conqueror is winning a lot of battles lately. He has expanded his kingdom to N cities which are numbered from 1 to N. The ith city has Wealth Wi. There are M roads connecting some of those cities. Now the King wants the whole kingdom to be connected so as to maintain unity within the kingdom. He gives some money to his Transport Minister Golu and instructs him to construct the required roads. But Golu has a plan of his own. He finds out that for constructing a road between city i and city j, the cost incurred is Wi*Wj. More the wealth of the cities more is the cost of constructing a road between them. Now, as all ministers are, Minister Golu is also corrupt and greedy. He wants to use the minimum amount of given money to fulfill King Kala’s requirement and keep the rest of the money for himself. As Minister Golu’s advisor, your task is to find out how much minimum money does he require to connect the kingdom?

Input

The first line contains the number of test case T. For each test case, the first line contains space separated integers N and M. The next line contains N space separated integers where the ith integer is the wealth of city i, i.e. Wi. The next M lines contains two integers X and Y denoting that there is road already present between cities X and Y.

Output

For each test case, you have to print the minimum money that Golu needs to spend to connect the whole kingdom.

Contraints

1<=T<=25

Subtask 1: (50 points)

1 <= N <=10^3
0<=M<=2x10^3
0<=Wi<=10^3

Subtask 2: (200 points)

1 <= N <=10^5
0<=M<=2x10^5
0<=Wi<=10^6

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

For the first case, minister Golu can contruct a road between city 2 and 3. i.e. the cost is W3 x W2. =. 5 x 3 = 15.

For the second test case, Golu can build a road between city 1 and city 3, i.e., the cost is W3 x W1 = 5 x 7 = 35.

Editor Image

?