EOJ Monthly 2021.9 Sponsored by TuSimple

C. 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