## Oriented Lamps

Points: 100
Time limit: 1.0s
Memory limit: 256M

Problem type

Given an $$N \times N$$ grid, and a bunch of lamps identified by $$(x_i, y_i)$$ positions, each lamp can be set either horizontally or vertically (but not both) and can propagate light in that direction up to a distance $$K$$.

What is the maximum distance $$1 \le K$$, such that when all the lamps are turned on, no cell in the grid is highlighted by $$2$$ or more lamps shooting light in the same direction?

You are free to configure the direction of each lamp independently as long as the condition is not broken.

#### Input Specification

First line contains 2 integers, $$2 \leq N \leq 10^9$$ and $$1 \leq M \leq 2000$$, size of the grid side, and number of lamps.

$$M$$ lines follow, each containing 2 integers $$1 \leq x, y \leq N$$ positions of the lamps

#### Output Specification

Print a single integer $$K$$ denoting the maximum distance, $$-1$$ if no configuration will allow you to do it, and inf if the distance can be as big as you want.

#### Sample Input

4 2
2 2
3 4

#### Sample Output

inf

#### Sample Input

3 6
1 3
1 2
1 1
3 2
3 1
3 3

#### Sample Output

-1

#### Notes

Each lamp, when turned on, will light up to $$2 * K + 1$$ cells (either horizontally or vertically), where K is the maximum distance for the lamps.