题目描述

2323年，随着科技的发展以及地球日趋严重的人口压力，人类开始大规模向火星移民。令人欣慰的是，移民工程的第一步取得了巨大的成功，已经在火星表面建立了$N$个移民站，其中第i个移民站的坐标是$(u_i, v_i)$。但是在进行后续的移民工作时，人们遇到了一个严峻的问题：如何选择新建的移民站的地址。经过调查确定，需要在火星上新建$M$个移民站，已知原有的第$i$个移民站和新建的第$j$个移民站之间信息传输的流量是$A_{i,j}$，新建的第$j$个移民站和第$k$个移民站之间信息传输的流量是$B_{j,k}$，同时假定，将一个单位流量的信息传输一个单位距离的费用是$1$，这里的距离定义为曼哈顿距离。两个点$(x_1, y_1)$和$(x_2, y_2)$的曼哈顿距离定义如下：

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

现在的问题是，给定原有的$N$个移民站的地址和信息流量传输矩阵$A$、$B$，需要你为这$M$个新的移民站选择地址，使得信息传输总费用最小。

输入格式

输入文件为locate1.in~locate10.in，第一行为两个整数$N$、$M$，表示原有移民站的数目和需要新建的移民站的数目。接下来的N行每行包含两个整数，表示原有的移民站的坐标；接下来$N$行每行包含$M$个整数，表示信息流量传输矩阵$A$；最后$M-1$行中，第$i$行包含$M-i$个整数，其中的第$j$个表示$B_{i,i+j}$。

输出格式

输出文件为locate1.out~locate10.out，locate?.out对应locate?.in的答案。输出的第一行为一个整数，表示你所计算出的信息传输费用。接下来的$M$行每行包含两个整数，其中第$i$行表示第$i$个新建的移民站的坐标。

3 1
1 5
2 4
3 6
1 2 3

9
2 5

提示

本题输入数据下载：百度网盘

【评分标准】

每个测试点单独评分。

对于每一个测试点，如果你给出的输出文件不合法，如文件格式错误、输出 解不符合要求等，该测试点得 0 分。否则设你的输出答案长度为 ans，对于不同的测试点，我们还设有 9 个评分相关的常数 c1 ≤ c2 ≤ c3 ≤ c4 ≤ c5 ≤ c6 ≤ c7 ≤ c8 ≤ c9 ≤ c10，你在该测试点中的得分由下列陈述得出：

• 如果 ans > c10，得0分。
• 如果 ans ≤ c10，得1分。
• 如果 ans ≤ c9，得2分。
• 如果 ans ≤ c8，得3分。
• 如果 ans ≤ c7，得4分。
• 如果 ans ≤ c6，得5分。
• 如果 ans ≤ c5，得6分。
• 如果 ans ≤ c4，得7分。
• 如果 ans ≤ c3，得8分。
• 如果 ans ≤ c2，得9分。
• 如果 ans ≤ c1，得10分。
• 如果 ans < c1，得12分。
• 如果满足多个条件，取得分最大者为最终得分。

【特别提示】

请妥善保存输入文件locate*.in 和你的输出locate*.out，及时备份，以免误删。☺