"The wolf loves the sheep, a love so crazy, who let them have a true romance; the wolf loves the sheep, it is not absurd, they say where there is love, there is a direction..."
Orez heard this song and thought: Wolves and sheep are so harmonious, why not try raising them together? He decided to do it immediately!
Orez's sheep and wolf enclosure can be viewed as an $n \times m$ grid of cells, and the edges of this matrix are already fenced. However, Drake soon discovered that a wolf is a wolf after all, and they are always drooling over the sheep; that song was just a touching legend. Therefore, Orez decided to add some more fences within the enclosure to keep the sheep and wolves separated.
Through careful observation, Orez found that both wolves and sheep have their own territories. If the wolves and sheep cannot stay in their own territories, they will become very irritable, which is not conducive to their growth.
Orez wants to add the shortest possible fence. Of course, this fence must first ensure that the territories of the wolves and sheep are not changed, and furthermore, the fence must be built completely, meaning it must be built along the boundaries of the unit cells and cannot be only partially constructed.
Input
The first line of the input contains two integers $n$ and $m$. The following $n$ lines each contain $m$ integers, where $1$ indicates that the cell belongs to the wolf's territory, $2$ indicates that it belongs to the sheep's territory, and $0$ indicates that the cell does not belong to any animal's territory.
Output
The output contains a single integer $ans$, representing the minimum length of the fence.
Examples
Input 1
2 2 2 2 1 1
Output 1
2
Constraints
- $10\%$ of the data: $n, m \le 3$
- $30\%$ of the data: $n, m \le 20$
- $100\%$ of the data: $n, m \le 100$