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.