4335. Connection

单点时限: 1.0 sec

内存限制: 256 MB

Now, little W gets a 01 matrix of size $N * M$. He wants to turn all elements in the matrix to 1. He can do the following operations:

  1. Turning any one element to 1 from 0 costs 4.

  2. If positions $(x1,y1), (x2,y1)$ and $(x1,y2)$ are 1, turning $(x2, y2)$ to 1 from 0 will cost 3.

He wants to know the minimum cost, please help him.

输入格式

The first line contains two positive integers $N$ and $M$. $(1 \leq N, M \leq 1000)$

The following $N$ lines represent the matrix with only 0 and 1.

输出格式

The answer.

样例

Input
2 5
10010
00001
Output
24
Input
6 6
010000
011010
110111
100101
110001
110100
Output
54

106 人解决,113 人已尝试。

110 份提交通过,共有 169 份提交。

2.0 EMB 奖励。

创建: 1 年,3 月前.

修改: 1 年,2 月前.

最后提交: 9 月,1 周前.

来源: N/A

题目标签
dsu