Description

现在 Cuber QQ 有一个 $n \times m$ 的 $01$ 矩阵，他想要将矩阵的所有位置都变成 $1$ 。他可以进行如下的操作：

• 把其中一个位置从 $0$ 变成 $1$ ，花费 $4$ ；

• 如果位置 $(x1, y1),(x2, y1),(x1, y2)(1 \le x1, x2 \le n, 1 \le y1, y2 \le m)$ 是 $1$ ，把 $(x2, y2)$ 从 $0$ 变成 $1$ 花费 $3$ 。

现在 Cuber QQ 想知道最小的花费是多少。

Format

Input

第一行包含两个整数 $n, m(1 ⩽ n, m ⩽ 1000)$ ，表示矩阵的大小。

接下来的 $n$ 行表示 $01$ 矩阵。

Output

输出一行一个整数，表示答案。

Samples

2 5 

10010 

00001

24

Limitation

$1 \le n , m \le 1000$

对于 $30$ %的数据， $1 \le n , m \le 10$

对于 $40$ %的数据， $1 \le n , m \le 100$

对于 $30$ %的数据， 无其他限制

1s, 512MB for each test case.