Description

In the year 2323, with technological advances and the increasingly severe population pressure on Earth, humanity began large-scale migration to Mars. Encouragingly, the first step of the migration project achieved great success, and $N$ immigration stations have already been established on the surface of Mars, where the $i$-th station is at coordinates $(u_i, v_i)$. However, when proceeding with subsequent migration work, people encountered a serious problem: how to choose the locations for the new immigration stations. After investigation, it has been determined that $M$ new immigration stations need to be built on Mars. It is known that the information transmission flow between the original $i$-th station and the new $j$-th station is $A_{i,j}$, and the information transmission flow between the new $j$-th station and the $k$-th new station is $B_{j,k}$. At the same time, assume that the cost to transmit one unit of flow over one unit of distance is $1$, where the distance is defined as the Manhattan distance. The Manhattan distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as follows:

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

Now the problem is: given the addresses of the $N$ existing immigration stations and the information flow matrices $A$ and $B$, you need to choose locations for these $M$ new immigration stations so that the total information transmission cost is minimized.

Input Format

The input files are locate1.in~locate10.in. The first line contains two integers $N$, $M$, representing the number of existing immigration stations and the number of new stations to be built. The next $N$ lines each contain two integers, representing the coordinates of the existing stations. The next $N$ lines each contain $M$ integers, representing the information flow matrix $A$. In the final $M-1$ lines, the $i$-th line contains $M-i$ integers, where the $j$-th of them represents $B_{i,i+j}$.

Output Format

The output files are locate1.out~locate10.out, where locate?.out corresponds to the answer for locate?.in. The first line of the output is an integer, representing the total information transmission cost you computed. The next $M$ lines each contain two integers; the $i$-th line represents the coordinates of the $i$-th newly built immigration station.

3 1
1 5
2 4
3 6
1 2 3

9
2 5

Hint

The input testdata for this problem can be downloaded from: Baidu Netdisk.

【Scoring Criteria】

Each test point is scored independently.

For each test point, if your output file is invalid (e.g., file format error, output not meeting requirements, etc.), you receive 0 points for that test point. Otherwise, let your answer be $ans$. For different test points, we also set 10 scoring-related constants satisfying $c_1 \le c_2 \le c_3 \le c_4 \le c_5 \le c_6 \le c_7 \le c_8 \le c_9 \le c_{10}$. Your score for that test point is determined by the following statements:

• If $ans > c_{10}$, you get 0 points.
• If $ans \le c_{10}$, you get 1 point.
• If $ans \le c_9$, you get 2 points.
• If $ans \le c_8$, you get 3 points.
• If $ans \le c_7$, you get 4 points.
• If $ans \le c_6$, you get 5 points.
• If $ans \le c_5$, you get 6 points.
• If $ans \le c_4$, you get 7 points.
• If $ans \le c_3$, you get 8 points.
• If $ans \le c_2$, you get 9 points.
• If $ans \le c_1$, you get 10 points.
• If $ans < c_1$, you get 12 points.
• If multiple conditions are satisfied, the highest applicable score is taken as the final score.

【Special Reminder】

Please properly save the input files locate*.in and your outputs locate*.out, and back them up in time to avoid accidental deletion. ☺

Translated by ChatGPT 5