One day, N rogues find a treaure map in accident, so they decide to go along with each other to hunt the treasure in an isolate island. This island can be considered as an undirected graph with V vertexes, each of which is a land. The edge between two vertexes means there is a road connecting to the correspond lands.
After a great effort, these rogues finally find 2*N lands which contain gold mines. They must divide the lands equally, so each rogue should get two mines. And several additional lands should be assigned to each rogue in order that he can reach one gold mine from the other one by merely passing the lands belonging to him. Being too selfish to share a land with each other, they have quarrelled about how to divide the lands for many days.
Being the guardian of this island, you must try your best to protect it. If you manage to make a plan to meet their requirement, the lands which are not assigned to any rogues can be protected. You know there is a price for each land, so you must maximize the sum of price of the lands not assigned.
Input consists of many test cases. The first line is a integer T which is the amount of cases. The first line of each case are two integer numbers V and E with 1 <= V <= 500 and 0 <= E <= V*(V-1)/2, where V is the amount of lands and E is the amount of roads. Next E lines each contains two numbers vi and vj which denotes there is a road between lands vi and vj. The next integer is N with 1 <= N <= 4, the amount of rouges. Then 2*N integers follow which denote the 2*N lands containing gold mines. The last V positive integers are price of all lands. Lands are numbered from 0 to V-1.
For each test case, print a line containing a single integer which is the maximum price not assigned when the rouges' requirement is met. Print -1 if no feasible assignment exists.
2 9 5 0 1 2 3 4 5 6 7 7 8 4 0 1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 1 9 0 4 0 1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 1
1 -1
Migrated from old NTUJ.
2009Harbin
| No. | Testdata Range | Score |
|---|