Mars Migration Station Placement Optimization

In the year 2323, humanity has successfully established N migration stations on the surface of Mars at coordinates \( (u_i, v_i) \). In order to facilitate further immigration, M new migration stations need to be built. The cost of transmitting one unit of information per unit Manhattan distance is 1. The Manhattan distance between two points \( (x_1,y_1) \) and \( (x_2,y_2) \) is defined as:

[ \mathrm{ManhattanDist}( (x_1, y_1), (x_2, y_2) ) = |x_1-x_2|+|y_1-y_2| ]

The information flow between an existing station \( i \) and a new station \( j \) is given by \( A_{i,j} \). Moreover, the flow between a new station \( j \) and a new station \( k \) is \( B_{j,k} \). The total cost is computed as the sum of the costs incurred over all these transmissions:

[ \text{TotalCost} = \sum_{i=1}^{N}\sum_{j=1}^{M} A_{i,j}\cdot \mathrm{ManhattanDist}((u_i,v_i),(x_j,y_j)) + \sum_{j=1}^{M}\sum_{k=1}^{M} B_{j,k}\cdot \mathrm{ManhattanDist}((x_j,y_j),(x_k,y_k)) ]

Your task is to choose the coordinates \( (x_j,y_j) \) for the M new migration stations (for \( j=1,2,\dots,M \)) such that the total transmission cost is minimized. It is guaranteed that an optimal solution exists. For simplicity, assume that the candidate coordinates for the new stations lie in the set of coordinates already occupied by the existing stations.

inputFormat

The first line contains two integers \( N \) and \( M \) separated by a space.

The next \( N \) lines each contain two integers \( u_i \) and \( v_i \), the coordinates of the existing migration stations.

The next \( N \) lines each contain \( M \) integers. The \( j \)th number in the \( i \)th line is \( A_{i,j} \), the flow between the \( i \)th existing station and the \( j \)th new station.

The next \( M \) lines each contain \( M \) integers. The \( k \)th number in the \( j \)th line is \( B_{j,k} \), the flow between the new station \( j \) and new station \( k \).

You may assume that all flows and coordinates are integers. Note that the candidate coordinates for new stations are restricted to the coordinates given in the list of existing stations.

outputFormat

Output the minimum total transmission cost on the first line. Then output M lines, each containing two integers, representing the chosen coordinates \( (x_j, y_j) \) for the new migration stations (in order from \( j=1 \) to \( M \)).

sample

1 1
0 0
5
0

0
0 0