Description

世界顶级 IT 公司 Oondex 即将进驻 Lineland！在经历了多年烦人的"该服务在您所在区域不可用"错误提示后，Lineland 的居民终于能够收听最流行的音乐、观看最新的病毒视频，并享受 Oondex 提供的诸多服务。

Lineland 可以看作一条实数坐标轴。该地区有独特的网络资费标准：连接两个相距 $d$ 公里的服务器，建立一条吞吐量为 $t$ Mbit/s 的网络通道需要花费 $d \cdot t$ 美元。

为了提供更好的用户体验，Oondex 计划在 Lineland 部署 $n$ 台服务器。这些服务器将执行常规的数据处理任务，需要彼此之间进行密集的网络交互。同时，这些服务器还将为外部用户提供服务，通过 Lineland 已有的 $m$ 台特殊 CDN 服务器（内容分发服务器）进行内容分发。

Oondex 的分析师已经确定：

• 对于每对服务器 $i$, $j$（$1 \leq i < j \leq n$），服务器 $i$ 和 $j$ 之间需要的吞吐量为 $d_{ij}$ Mbit/s
• 对于每对服务器 $i$ 和 CDN 服务器 $k$（$1 \leq i \leq n$；$1 \leq k \leq m$），服务器 $i$ 和 CDN 服务器 $k$ 之间需要的吞吐量为 $c_{ik}$ Mbit/s

给定 CDN 服务器的位置 $a_k$（$1 \leq k \leq m$），确定 Oondex 服务器的部署位置 $x_i$（$1 \leq i \leq n$），使得部署成本最小。形式化地说，确定 $x_i$ 使得成本值 $v = \sum\limits_{1 \leq i < j \leq n} |x_i - x_j| \cdot d_{ij} + \sum\limits_{\substack{1 \leq i \leq n \\ 1 \leq k \leq m}} |x_i - a_k| \cdot c_{ik}$ 最小。允许多台服务器（包括 Oondex 服务器和 CDN 服务器）部署在同一位置。

Input Format

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 70$）——需要部署的 Oondex 服务器数量和已有的 CDN 服务器数量。

第二行包含 $m$ 个整数 $a_1, a_2, \ldots, a_m$（$0 \leq a_k \leq 10^6$）——现有 CDN 服务器的位置。

接下来的 $n$ 行，第 $i$ 行包含 $m$ 个整数 $c_{i1}, c_{i2}, \ldots, c_{im}$，其中 $c_{ik}$（$0 \leq c_{ik} \leq 50$）表示第 $i$ 台 Oondex 服务器与第 $k$ 台 CDN 服务器之间的吞吐量。

最后的 $n$ 行，第 $i$ 行包含 $n$ 个整数 $d_{i1}, d_{i2}, \ldots, d_{in}$（$0 \leq d_{ij} \leq 50$；$d_{ij} = d_{ji}$；$d_{ii} = 0$），其中 $d_{ij}$ 表示第 $j$ 台 Oondex 服务器与第 $i$ 台 Oondex 服务器之间的吞吐量。

Output Format

第一行输出值 $v$——部署 $n$ 台 Oondex 服务器的最小可能成本。

第二行输出 $n$ 个整数 $x_1, x_2, \ldots, x_n$，其中 $x_i$（$0 \leq x_i \leq 10^6$）表示第 $i$ 台 Oondex 服务器应该部署的位置。可以证明存在满足 $x_i$ 范围限制（范围和整数性）的最优解。

3 4
20 14 5 2
1 2 3 0
3 0 3 0
0 0 0 20
0 15 0
15 0 0
0 0 0

78
9 9 2

Hint

翻译由 DeepSeek V3 完成