The world's best IT company Oondex is coming to Lineland! After years of facing annoying "This service is not available in your area" error messages, Linelanders will finally be able to listen to the most popular music, watch fresh viral videos and use lots of other opportunities provided by Oondex's services.
Lineland can be seen as a real coordinate line. It has unusual network tariffs: connecting two servers $d$ kilometers apart from each other with a network channel of throughput $t$ Mbit/s costs $d dot.op t$ dollars.
In order to provide better user experience, Oondex is going to place $n$ servers in Lineland. These servers will be performing regular data processing activities which requires intense pairwise network interaction between these servers. At the same time, these servers are going to serve external users using $m$ special CDN servers (which are specialized content delivery servers) already present in Lineland.
Analysts of Oondex determined for each pair $i$, $j$ ($1 <= i < j <= n$) the required throughput $d_{i j}$ Mbit/sec between servers $i$ and $j$, and also for each pair $i$, $k$ ($1 <= i <= n$; $1 <= k <= m$) the required throughput $c_{i k}$ Mbit/sec between server $i$ and CDN server $k$.
Given the locations of CDN servers $a_k$ ($1 <= k <= m$), determine the locations $x_i$ ($1 <= i <= n$) such that the cost of placing servers into them is the minimum possible. Formally, determine $x_i$ such that the cost value of $v = sum limits_{1 <= i < j <= n} | x_i -x_j | dot.op d_{i j} + sum limits_{substack 1 <= i <= n \
1 <= k <= m} | x_i -a_k | dot.op c_{i k}$ is the minimum possible. Multiple servers (both Oondex and CDN) may be located at the same point.
The first line contains two integers $n$ and $m$ ($1 <= n, m <= 70$) — the number of Oondex servers to place and the number of existing CDN servers.
The second line contains $m$ integers $a_1, a_2, \\dots, a_m$ ($0 <= a_k <= 10^6$) — the locations of existing CDN servers.
The $i$-th of the next $n$ lines contains $m$ integers $c_{i 1}, c_{i 2}, \\dots, c_{i m}$ where $c_{i k}$ ($0 <= c_{i k} <= 50$) is the throughput between $i$-th Oondex server and the $k$-th CDN server.
Finally, the $i$-th of the next $n$ lines contains $n$ integers $d_{i 1}, d_{i 2}, \\dots, d_{i n}$ ($0 <= d_{i j} <= 50$; $d_{i j} = d_{j i}$; $d_{i i} = 0$) where $d_{i j}$ is the throughput between $j$-th Oondex server and the $i$-th Oondex server.
On the first line output the value $v$ — the minimum possible cost of placing $n$ Oondex servers.
On the second line output $n$ integers $x_1, x_2, \\dots, x_n$ where $x_i$ ($0 <= x_i <= 10^6$) — the coordinates at which the $i$-th Oondex server should be placed. It can be proven that an optimum answer satisfying these restrictions on $x_i$ (range and integrality) exists.
## Input
The first line contains two integers $n$ and $m$ ($1 <= n, m <= 70$) — the number of Oondex servers to place and the number of existing CDN servers.The second line contains $m$ integers $a_1, a_2, \\dots, a_m$ ($0 <= a_k <= 10^6$) — the locations of existing CDN servers.The $i$-th of the next $n$ lines contains $m$ integers $c_{i 1}, c_{i 2}, \\dots, c_{i m}$ where $c_{i k}$ ($0 <= c_{i k} <= 50$) is the throughput between $i$-th Oondex server and the $k$-th CDN server.Finally, the $i$-th of the next $n$ lines contains $n$ integers $d_{i 1}, d_{i 2}, \\dots, d_{i n}$ ($0 <= d_{i j} <= 50$; $d_{i j} = d_{j i}$; $d_{i i} = 0$) where $d_{i j}$ is the throughput between $j$-th Oondex server and the $i$-th Oondex server.
## Output
On the first line output the value $v$ — the minimum possible cost of placing $n$ Oondex servers.On the second line output $n$ integers $x_1, x_2, \\dots, x_n$ where $x_i$ ($0 <= x_i <= 10^6$) — the coordinates at which the $i$-th Oondex server should be placed. It can be proven that an optimum answer satisfying these restrictions on $x_i$ (range and integrality) exists.
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of Oondex servers and CDN servers, respectively.
Let $ \mathbf{a} = (a_1, \dots, a_m) \in \mathbb{R}^m $ be the fixed locations of CDN servers.
Let $ C = (c_{ik}) \in \mathbb{R}^{n \times m} $ be the throughput matrix between Oondex server $ i $ and CDN server $ k $.
Let $ D = (d_{ij}) \in \mathbb{R}^{n \times n} $ be the symmetric throughput matrix between Oondex servers $ i $ and $ j $, with $ d_{ii} = 0 $ and $ d_{ij} = d_{ji} $.
Let $ \mathbf{x} = (x_1, \dots, x_n) \in \mathbb{R}^n $ be the decision variables representing the locations of Oondex servers.
**Constraints**
1. $ 1 \leq n, m \leq 70 $
2. $ 0 \leq a_k \leq 10^6 $ for all $ k \in \{1, \dots, m\} $
3. $ 0 \leq c_{ik} \leq 50 $ for all $ i \in \{1, \dots, n\}, k \in \{1, \dots, m\} $
4. $ 0 \leq d_{ij} \leq 50 $ for all $ i,j \in \{1, \dots, n\} $, with $ d_{ij} = d_{ji} $, $ d_{ii} = 0 $
5. $ x_i \in \mathbb{Z} $ and $ 0 \leq x_i \leq 10^6 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Minimize the total cost:
$$
v = \sum_{1 \leq i < j \leq n} |x_i - x_j| \cdot d_{ij} + \sum_{i=1}^n \sum_{k=1}^m |x_i - a_k| \cdot c_{ik}
$$