[CTSC2009] 移民站选址

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

本题输入数据下载：[百度网盘](https://pan.baidu.com/s/1hEbcB45kL25wbXqEeew7Yg) **【评分标准】** 每个测试点单独评分。 对于每一个测试点，如果你给出的输出文件不合法，如文件格式错误、输出 解不符合要求等，该测试点得 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*，及时备份，以免误删。☺