It's a trend to build a distributed computing system in the Kerker country in order to take computing Ramsey number R(5,5) in practice. There are many computing nodes in the system and each of them is a single PC or a virtual machine. In addition, these computing nodes are communicated through the network in Kerker country. On these computing nodes, there are three versions (version 1.0, 2.0, and 3.0) available to install on each node and have different costs depend on where the computing node is located. Moreover, it requires another cost when communicating between different computing nodes with different versions. For two computing nodes with a network edge connecting and with versions x and y, it requires a cost of c*(x-y)2 for this edge, where c is a location-independent constant, but dependent to different systems.
Given the network in the system and the costs for building each of the three versions at every computing nodes. Please find the minimum total cost for building such a system.
The first line contains an integer T indicating the number of the test cases. The first line of each test case contains two integers n (1<=n<=50) and c (1<=c<=100,000) indicating the number of computing nodes and the mysterious cost for this system defined in the description. In each of the next n lines contains three integers Vi_1, Vi_2, Vi_3 indicating install version x for the computing node i costs Vi_x. The next line contains an integer m indicating the number of network edges in the system. Each of the next m lines contains two integers u and v indicating the edge connectes between node u and node v.
For each test case, please output the minimum total cost for building such a system. You may assume that the answer and each number in the input does not exceed 10,000,000.
3 1 1 1 2 3 0 4 1 5 25 30 15 20 35 5 25 30 15 20 35 3 1 2 2 3 2 4 4 100 0 5555 5555 5555 0 5555 5555 5555 0 0 5555 5555 3 1 2 2 3 2 4
1 40 300
Migrated from old NTUJ.
Maximum Cup 2008 problem E
| No. | Testdata Range | Score |
|---|