世界顶尖的 IT 公司 Oondex 即将入驻 Lineland！在经历了多年令人恼火的“您所在的地区无法使用此服务”错误提示后，Lineland 的居民终于能够聆听最流行的音乐、观看最新的热门视频，并享受 Oondex 服务提供的许多其他机会。

Lineland 可以被看作一条实数坐标轴。它有着不寻常的网络资费：将相距 $d$ 公里的两个服务器用吞吐量为 $t$ Mbit/s 的网络通道连接起来，需要花费 $d \cdot t$ 美元。

为了提供更好的用户体验，Oondex 计划在 Lineland 放置 $n$ 个服务器。这些服务器将进行常规的数据处理活动，这需要这些服务器之间进行频繁的两两网络交互。同时，这些服务器还将利用 Lineland 中已有的 $m$ 个专用 CDN 服务器（即专门的内容分发服务器）来为外部用户提供服务。

Oondex 的分析师确定了每对服务器 $i, j$ ($1 \le i < j \le n$) 之间所需的吞吐量 $d_{ij}$ Mbit/s，以及每个服务器 $i$ 与 CDN 服务器 $k$ ($1 \le i \le n; 1 \le k \le m$) 之间所需的吞吐量 $c_{ik}$ Mbit/s。

已知 CDN 服务器的位置 $a_k$ ($1 \le k \le m$)，确定服务器的位置 $x_i$ ($1 \le i \le n$)，使得放置这些服务器的总开销最小。形式化地，确定 $x_i$ 使得开销值 $v = \sum_{1 \le i < j \le n} |x_i - x_j| \cdot d_{ij} + \sum_{\substack{1 \le i \le n \\ 1 \le k \le m}} |x_i - a_k| \cdot c_{ik}$ 最小。多个服务器（包括 Oondex 服务器和 CDN 服务器）可以位于同一个点上。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 70$) —— 计划放置的 Oondex 服务器数量和现有的 CDN 服务器数量。

第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$ ($0 \le a_k \le 10^6$) —— 现有 CDN 服务器的位置。

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $c_{i1}, c_{i2}, \dots, c_{im}$，其中 $c_{ik}$ ($0 \le c_{ik} \le 50$) 是第 $i$ 个 Oondex 服务器与第 $k$ 个 CDN 服务器之间的吞吐量。

最后，接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $d_{i1}, d_{i2}, \dots, d_{in}$ ($0 \le d_{ij} \le 50; d_{ij} = d_{ji}; d_{ii} = 0$)，其中 $d_{ij}$ 是第 $j$ 个 Oondex 服务器与第 $i$ 个 Oondex 服务器之间的吞吐量。

输出格式

第一行输出一个值 $v$ —— 放置 $n$ 个 Oondex 服务器的最小可能开销。

第二行输出 $n$ 个整数 $x_1, x_2, \dots, x_n$，其中 $x_i$ ($0 \le x_i \le 10^6$) —— 第 $i$ 个 Oondex 服务器应当放置的坐标。可以证明，存在满足这些关于 $x_i$ 的限制（范围和整数性）的最优解。

样例

输入 1

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

输出 1

78
9 9 2