光的流动开始漂移分离，作为回应，人们建造了桥梁来跨越不断扩大的距离。 为了重新统一破碎的岛屿，他们建造了从岛屿中心延伸到最边缘的结构。 旨在完成这次重新连接的最终结构被称为 Crosslink（交叉链接）——但这座桥梁从未完工。 沿着他们曾经试图团结的破碎流光的遗迹，修复那座未完成的桥梁。
在岛上，有一个大小为 $N \times M$ 的网格。从上数第 $r$ 行、从左数第 $c$ 列的单元格记为 $(r, c)$。
在 $N \times M$ 个单元格中，有一些已经包含陆地。人们希望添加更多的陆地以形成一个 crosslink——这是一个由陆地单元格组成的连通区域，且该区域触及网格的所有四个边界：上、下、左、右。
正式地，如果一个网格单元格集合 $S$ 满足以下条件，则被称为一个 crosslink：
- 每个单元格 $(r, c) \in S$ 都包含陆地。
- 对于 $S$ 中的任意两个不同的单元格 $a, b \in S$，存在一条路径 $a = p_1 \to p_2 \to \dots \to p_k = b$，满足 $\{p_1, p_2, \dots, p_k\} \subset S$，且 $p_i$ 和 $p_{i+1}$ 在上、下、左、右方向上相邻（$1 \le i \le k - 1$）。
- 存在一个整数 $c$（$1 \le c \le M$）使得 $(1, c) \in S$。
- 存在一个整数 $c$（$1 \le c \le M$）使得 $(N, c) \in S$。
- 存在一个整数 $r$（$1 \le r \le N$）使得 $(r, 1) \in S$。
- 存在一个整数 $r$（$1 \le r \le N$）使得 $(r, M) \in S$。
下图展示了一个包含有效 crosslink 的网格示例。阴影单元格表示陆地，而未阴影单元格表示空格。如第三个示例所示，并非所有陆地单元格都需要是 crosslink 的一部分。
接下来的三个网格不包含 crosslink。例如，在第三个网格中，不存在一个既能到达左边界又能到达右边界的起点，因此它不包含 crosslink。
在不同位置放置新陆地的代价可能有所不同。考虑以下示例：
在最左边的图像中，黑色单元格表示现有的陆地，而未阴影单元格中的数字表示在这些位置放置新陆地的代价。
通过添加红色所示的陆地，可以形成一个 crosslink，总代价为 $4 + 4 = 8$。然而，如黄色所示放置陆地可以形成一个有效的 crosslink，且总代价更低，为 $1 + 2 + 1 + 2 + 1 = 7$，这是本例中的最小代价。另一方面，如绿色所示放置陆地仅需代价 $4 + 2 = 6$，但由于它不包含 crosslink，因此不是一个有效的解。
岛民们希望找到放置陆地并形成有效 crosslink 所需的最小总代价。
输入格式
第一行包含两个整数 $N, M$，表示网格的大小。
接下来的 $N$ 行，每行包含字符 $C_{i,1}, C_{i,2}, \dots, C_{i,M}$，表示网格的状态。字符的含义如下：
- 如果 $C_{i,j}$ 为
0，则单元格 $(i, j)$ 已经包含陆地。 - 如果 $C_{i,j}$ 是
1到9的数字，则单元格 $(i, j)$ 为空，且在此处放置陆地的代价为对应的数字。 - 如果 $C_{i,j}$ 是大写字母
A到Z之一，则单元格 $(i, j)$ 为空，且在此处放置陆地的代价分别为 $10, 11, \dots, 35$。
输出格式
输出创建 crosslink 所需放置陆地的最小总代价。
数据范围
- $2 \le N \le 1000$
- $2 \le M \le 1000$
- $C_{i,j}$ 为数字或大写字母（$1 \le i \le N, 1 \le j \le M$）
子任务
- 子任务 1（8 分）：$N \le 4, M \le 4$
- 子任务 2（3 分）：$C_{i,j} = \text{'1'}$（$1 \le i \le N, 1 \le j \le M$）
- 子任务 3（11 分）：对于偶数 $i$，$C_{i,j} = \text{'0'}$（$1 \le i \le N, 1 \le j \le M$）
- 子任务 4（42 分）：$N \le 100, M \le 100$
- 子任务 5（18 分）：$N \le 700, M \le 700$
- 子任务 6（18 分）：无附加限制。
样例
输入样例 1
5 5 00280 20358 10901 24400 12105
输出样例 1
7
输入样例 2
5 7 QTVPU0Z 02X010Y Y0R2T0X Z301Y40 W0PUXVZ
输出样例 2
13