Marisa has discovered that there are $n$ wild mushrooms growing in her garden, which has a size of $m \times m$. However, two mushrooms that are adjacent (i.e., share an edge) can conflict with each other as they grow larger. To prevent this, Marisa needs to pick some mushrooms so that no two adjacent mushrooms are kept. Your task is to determine the maximum number of mushrooms that Marisa can keep while satisfying this condition.
### Input
- The first line contains two integers $n, m$.
- The next $n$ lines, each line contains two integers $x, y$, the mushroom located on row $x$ and column $y$.
### Output
- Print the maximum number of mushrooms Marisa can keep.
### Constraints
- $1 \le n \le 5000$.
- $1 \le m \le 200$.
- $1 \le x, y \le m$.
### Example
Input:
```
4 2
1 1
1 2
2 1
2 2
```
Output:
```
2
```
