Oriented Lamps

Submit solution

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


Sample Input

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

Sample Output



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.


There are no comments at the moment.