URI Online Judge | 1614

Help the Tourist

By Daniel Chino, USP - São Carlos BR Brazil

Timelimit: 1

Luís is on vacations and would like to visit the tourist attractions of Manhattan in the next K days. Trough a map, he knows the location of the N tourist attractions and the M subway stations of the city. To enjoy the tours, he will visit only one point per day. Although, he is pretty lazy and would like to walk the least distance possible between the tourist attraction and one subway station.

In another words, choose K distinct pairs of tourist attractions and subway stations, such that the sum of their distance is minimized. The distance is calculated using the Manhattan distance, it is, given a point A and a point B, the distance between them is defined by: D(A,B) = |A_x - B_x| + |A_y - B_y|. More information about this distance: http://en.wikipedia.org/wiki/Taxicab_geometry .

Input

The first line contains an integer T (T = 100) indicating the number of test cases.

In the first line of each case, there will be the integers N (1 ≤ N), M (M ≤ 100) and K (1 ≤ K ≤ min(10, N*M)). In the next N lines there will be the tourist attractions locations and in the next M lines the locations of the subway stations, all given by a pair (x, y)(0 <= x,y <= 1000* or 0 <= x,y <= 105** ) of coordinates. All coordinates are unique.

*For around 90% of the cases;

**For the other cases.

Output

Output the sum of the distances Luís walked in each case. Remember that you should minimize this value.

Sample Input Sample Output

3

1 2 1

0 0

2 2

1 1

2 1 2

2 2

2 3

2 4

5 4 5

1 1

2 3

4 2

5 4

6 1

1 2

2 1

2 6

4 4

2

3

7