In the year 2323, with the development of technology and the increasingly severe population pressure on Earth, humanity has begun large-scale migration to Mars. Fortunately, the first step of the migration project has been a huge success, with $n$ migration stations already established on the Martian surface, where the $i$-th station has coordinates $(u_i, v_i)$. However, during subsequent migration efforts, people encountered a serious problem: how to choose the locations for new migration stations. After investigation, it was determined that $M$ new migration stations need to be built on Mars. It is known that the information transmission flow between the $i$-th existing station and the $j$-th new station is $A_{ij}$, and the information transmission flow between the $j$-th new station and the $k$-th new station is $B_{jk}$. It is also assumed that the cost of transmitting one unit of information over one unit of distance is 1, where 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:

$$ManhattanDist( (x_1, y_1), (x_2, y_2) ) = |x_1 - x_2| + |y_1 - y_2|$$

The problem is, given the addresses of the $N$ existing migration stations and the information flow transmission matrices $A$ and $B$, you need to choose locations for these $M$ new migration stations to minimize the total cost of information transmission.

Input

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

Output

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

Examples

Input 1

3 1
1 5
2 4
3 6
1 2 3

Output 1

9
2 5

Subtasks

Each test case is scored individually.

For each test case, if the output file you provide is invalid (e.g., incorrect file format, solution does not meet requirements, etc.), the test case receives 0 points. Otherwise, let the length of your output answer be ans. For different test cases, we have 9 scoring-related constants $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 this test case is determined by the following statements:

• If ans > $c_{10}$, score 0.
• If ans $\le c_{10}$, score 1.
• If ans $\le c_9$, score 2.
• If ans $\le c_8$, score 3.
• If ans $\le c_7$, score 4.
• If ans $\le c_6$, score 5.
• If ans $\le c_5$, score 6.
• If ans $\le c_4$, score 7.
• If ans $\le c_3$, score 8.
• If ans $\le c_2$, score 9.
• If ans = $c_1$, score 10.
• If ans < $c_1$, score 12.

If multiple conditions are met, the highest score is taken as the final score.

Interaction

There is a checker file in the user directory. Use the method checker case_no, where case_no represents the number of the test case. It returns the following information:

1. Input file does not exist: The checker cannot find the corresponding input file.
2. Output file does not exist: The checker cannot find the corresponding output file.
3. Output format error: Your output does not match the required format.
4. Your output is incorrect: The actual transmission cost required by your scheme is not equal to the transmission cost in your output file.
5. Your output is correct: Your output result is correct, and you can proceed to the next step of scoring.

Note

Please keep the input files locate*.in and your output files locate*.out safe and back them up in time to avoid accidental deletion.