G. War
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Turning enemies into friends makes one invincible.
—Salt & Pepper Chicken

Given a grid with $$$n$$$ rows and $$$m$$$ columns, the status of the cell in the $$$i$$$-th row and $$$j$$$-th column can be denoted by $$$a_{i,j}$$$. If $$$a_{i,j}=0$$$, the cell is occupied by allies. If $$$a_{i,j}=1$$$, the cell is occupied by enemies.

To convert all cells into allied cells, you can perform the following operation:

  • Select an enemy cell adjacent to an allied cell $$$^{\dagger}$$$ or an enemy cell adjacent to the boundary $$$^{\ddagger}$$$. Suppose there are $$$w$$$ enemy cells adjacent to the selected cell; you can convert this cell into an allied one at a cost of $$$w+1$$$.

What is the minimum cost required to convert all enemy cells into allied cells if we use the optimal strategy?

$$$^{\dagger}$$$ Denote the cell in the $$$i$$$-th row and $$$j$$$-th column as $$$(i,j)$$$. Two cells $$$(a,b)$$$ and $$$(c,d)$$$ are adjacent if and only if $$$|a-c| + |b-d| = 1$$$.

$$$^{\ddagger}$$$ Denote the cell in the $$$i$$$-th row and $$$j$$$-th column as $$$(i,j)$$$. A cell $$$(i,j)$$$ is adjacent to the boundary if and only if $$$i=1$$$, $$$j=1$$$, $$$i=n$$$, or $$$j=m$$$.

Input

There is only one test case in each test file.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 1000$$$), representing the number of rows and columns of the grid.

In the next $$$n$$$ lines, the $$$i$$$-th one contains $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$a_{i,j} \in \{0, 1\}$$$), representing the status of the grid cells.

Output

Output a single integer, the minimum cost to convert all enemy cells into allied cells.

Example
Input
5 5
0 0 0 0 0
0 0 0 1 0
0 1 1 1 0
0 0 1 0 0
0 0 0 0 0
Output
9
Note

In the sample case, we can first convert the cell in the $$$3$$$-rd row and $$$3$$$-rd column at a cost of $$$3+1=4$$$. Then, we convert the cell in the $$$3$$$-rd row and $$$4$$$-th column at a cost of $$$1+1=2$$$. The remaining three cells can be converted in any order, requiring a total cost of $$$9$$$. It can be proven that there is no better strategy.