题目描述

莫莉斯·乔是圣域里一个叱咤风云的人物，他凭借着自身超强的经济头脑，牢牢控制了圣域的石油市场。

圣域的地图可以看成是一个 $n\times m$ 的矩阵。每个整数坐标点 $(x, y)$ 表示一座城市（$1\le x\le n,1\le y\le m$）。两座城市间相邻的定义为：对于城市 $(A_x, A_y)$ 和城市 $(B_x, B_y)$，满足 $(A_x - B_x)^2 + (A_y - B_y)^2 = 1$。

由于圣域的石油贸易总量很大，莫莉斯意识到不能让每笔石油订购单都从同一个油库里发货。为了提高效率，莫莉斯·乔决定在其中一些城市里建造油库，最终使得每一个城市 $X$ 都满足下列条件之一：

1. 该城市 $X$ 内建有油库.
2. 某城市 $Y$ 内建有油库，且城市 $X$ 与城市 $Y$ 相邻。

与地球类似，圣域里不同城市间的地价可能也会有所不同，所以莫莉斯想让完成目标的总花费尽可能少。如果存在多组方案，为了方便管理，莫莉斯会选择建造较少的油库个数。

输入格式

第一行两个正整数 $n,m$（$n \times m \le 50$ 且 $m\le n$），表示矩阵的大小。

接下来一个 $n$ 行 $m$ 列的矩阵 $F$，$F_{i, j}$表示在城市 $(i,j)$ 建造油库的代价。

输出格式

输出两个数，建造方案的油库个数和方案的总代价。

3 3
6 5 4
1 2 3
7 8 9

3 6

提示

对于 $30\%$ 数据满足 $n \times m \le 25$;
对于 $100\%$ 数据满足 $n \times m \le 50,0 \le F_{i, j} \le 10 ^ 5$。