Kingdom Of Monkeys

This is a story in Zimbo, the kingdom officially made for monkeys. Our Code Monk visited Zimbo and declared a challenge in the kingdom, thus spoke to all the monkeys:

You all have to make teams and go on a hunt for Bananas. The team that returns with the highest number of Bananas will be rewarded with as many gold coins as the number of Bananas with them. May the force be with you!

There are N monkeys in the kingdom. Each monkey who wants to team up with another monkey has to perform a ritual. A total of M rituals are performed. Each ritual teams up two monkeys. If Monkeys A and B teamed up, and Monkeys B and C teamed up, then Monkeys A and C are also in the same team.

You are given an array A, where A_i is the number of bananas gathered by the ith monkey.

Find the number of gold coins that our Monk should set aside for the prize.

Input Specification

The first line of the input contains an integer T (1 ≤ T ≤ 10). T test cases follow. The first line of each test case contains two space-separated integers N and M (1 ≤ N ≤ 10⁵, 0 ≤ M ≤ 10⁵). M lines follow. Each of the M lines contains two integers X_i and Y_i, the indexes of monkeys that perform the ith ritual. The last line of the test case contains N space-separated integers, constituting the array A (0 ≤ A_i ≤ 10¹²).

Output Specification

Print the answer to each test case in a new line.

Sample Input

1. 1
2. 4 3
3. 1 2
4. 2 3
5. 3 1
6. 1 2 3 5

download as text file

Output for Sample Input

1. 6

download as text file

Sample Explanation

Monkeys 1, 2, and 3 are in the same team. They gather 1 + 2 + 3 = 6 bananas. Monkey 4 is a team. It gathers 5 bananas. Therefore, the number of gold coins (highest number of bananas by a team) is 6.