A company has ~n~ offices labeled from ~1~ to ~n~. This company is creating an interconnected network between the offices (one may call it the company's inter-net) by setting up several two-way connections between offices, such that any distinct offices ~i~ and ~j~ (~i \neq j~) can connect to each other via these connection.

There are ~k~ inter-net providers supplying a total of ~m~ possible connections, the ~i~-th of which connects office ~u_i~ with office ~v_i~, is operated by the ~c_i~-th provider, and costs ~p_i~ dong~^\dagger~ to set up (note that there may be several connections between any two offices).

Furthermore, to boost competition, all ~k~ providers are offering customer loyalty program; specifically, if the company pays the ~j~-th provider an amount more than ~s_j~, the ~j~-th provider will apply a ~50\%~-off discount for the extra amount. Formally, this means that the provider will charge ~x_j - \frac{\max(0, x_j - s_j)}{2}~, where ~x_j~ is the total cost incurred to this provider.

Find the cheapest way to connect all the offices. Since this number times ~2~ can be proven to be an integer, please output the cheapest cost multiplied by ~2~.

~^\dagger~ ~1~ million dong equals approximately ~420~ Norwegian Kroner.

Input

Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 100~). The description of each test case is as follows.

The first line contains three integers ~n~, ~m~, and ~k~ (~2 \leq n \leq 1000~, ~n - 1 \leq m \leq 5 \cdot 10^5~, ~1 \leq k \leq 10~) —the number of offices, the number of possible connections, and the number of inter-net providers.

The ~i~-th line of the next ~m~ lines contains four integers ~u_i~, ~v_i~, ~c_i~, ~p_i~ (~1 \leq u_i, v_i \leq n~, ~u_i \neq v_i~, ~1 \leq c_i \leq k~, ~1 \leq p_i \leq 10^9~) describing the ~i~-th connection.

The last line contains ~k~ integers ~s_1, s_2, \cdots, s_k~ (~1 \leq s_i \leq 10^9~) describing the customer loyalty program of the ~k~ providers.

For each test case, it is guaranteed that there is at least one way to set up the connections such that all ~n~ offices are (directly or indirectly) connected.

The sum of ~n~ across all test cases is guaranteed not to exceed ~1000~, and the sum of ~m~ is guaranteed not to exceed ~5 \cdot 10^5~.

Output

For each test case, output one integer —the minimum cost (in dong) for setting up an interconnected network multiplied by ~2~.

Scoring

Sample Input 1

4
3 4 2
1 2 1 3
2 3 1 5
1 2 2 4
1 3 2 4
5 6
3 4 2
1 2 1 3
2 3 1 5
1 2 2 4
1 3 2 4
1 1
5 7 3
1 5 3 100
1 2 1 5
4 5 1 5
1 3 2 7
2 3 3 10
1 2 2 4
4 5 2 4
5 20 100
2 3 3
1 2 1 5
1 2 2 6
1 2 3 7
6 2 2

Sample Output 1

13
9
225
8

Notes

For the first test case, the illustration below represents the allowed connections for installation, with the red connections belonging to provider ~1~ and the blue connections belonging to provider ~2~. For ~s = [5, 6]~, we should install the highlighted connections. The total cost pre-discount to be paid for provider ~1~ and provider ~2~ respectively is ~[8, 0]~, so the total cost post-discount is ~\left(8 - \frac{\max(0, 8 - 5)}{2}\right) + \left(0 - \frac{\max(0, 0 - 6)}{2}\right) = \frac{13}{2}~.

For the second test case, the allowed connections for installation are similar to the first test case. For ~s = [1, 1]~, we should install the highlighted connections. The total cost pre-discount to be paid for provider ~1~ and provider ~2~ respectively is ~[3, 4]~, so the total cost post-discount is ~\left(3 - \frac{\max(0, 3 - 1)}{2}\right) + \left(4 - \frac{\max(0, 4 - 1)}{2}\right) = \frac{9}{2}~.