---
# System prepended metadata

title: Expedition

---

# Expedition

King Chandragupta is waging wars to expand his kingdom. His army is powerful enough to win every battle.

On a single day, Chandragupta can simultaneously wage wars on his neighboring kingdoms (i.e., the kingdoms which are in the North, South, East, and West directions).

Given a map of `M x N` regions, where **1** indicates Chandragupta's kingdom, **0** indicates other kingdoms and **x** indicates barren lands (where no one lives). Find out how many days king Chandragupta require to occupy all the kingdoms on the given map.

Write a program that reads a matrix `M x N` which represents the map and prints the number of days king Chandragupta require to occupy all the kingdoms.

---

#### Input

The first line of input contains two space-separated integers representing `M` and `N` respectively.
The next `M` lines of input contain space-separated characters. (Characters will be either **1**, **0**, or **x**)

---

#### Output

The output should be a single line containing an integer that is the number of days king Chandragupta require to occupy all the kingdoms.

---

#### Explanation

For example, if the given `M = 3`, `N = 3` and the next `M` lines are,

```
0 1 0
0 0 x
0 0 x
```

- On **Day 1**, the war is waged on the neighboring kingdoms (i.e., the kingdoms which are in the North, South, East, and West directions to Chandragupta's kingdom).

  - In this case, war is waged on three kingdoms and by the end of the first-day king Chandragupta will have **4** kingdoms.

  ```
  1 1 1
  0 1 x
  0 0 x
  ```

- On **Day 2**, the war is waged on the neighboring kingdoms (i.e., the kingdoms which are in the North, South, East, and West directions to Chandragupta's kingdoms).

  - In this case, war is waged on two kingdoms and by the end of the second-day king Chandragupta will have **6** kingdoms.

  ```
  1 1 1
  1 1 x
  0 1 x
  ```

- By the end of **Day 3**, the remaining one kingdom is occupied and king Chandragupta will have **7** kingdoms

  ```
  1 1 1
  1 1 x
  1 1 x
  ```

- So, king Chandragupta needs **3** days to occupy all the kingdoms.

The output should be **3**.

#### Test Cases

**Sample Input - 1**

**Input:**


```
3 3
0 1 0
0 0 x
0 0 x
```

**Output:** 3

---

**Sample Input - 2**

**Input:**

```
6 6
1 0 0 0 0 0
x x x x x 0
0 0 0 0 x 0
0 x 0 0 x 0
0 x x x x 0
0 0 0 0 0 0
```

**Output:** 22

----

**Sample Input - 3**

**Input:**

```
8 11
1 x 0 0 0 x 0 0 0 x 0
0 x 0 x 0 x 0 x 0 x 0
0 x 0 x 0 x 0 x 0 x 0
0 x 0 x 0 x 0 x 0 x 0
0 x 0 x 0 x 0 x 0 x 0
0 x 0 x 0 x 0 x 0 x 0
0 x 0 x 0 x 0 x 0 x 0
0 0 0 x 0 0 0 x 0 0 0
```

**Output:** 52

---

**Sample Input - 4**

**Input:**

```
14 9
1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1
```

**Output:** 10