Description

Farmer John (FJ) has an $n \times n$ farm ($1 \le n \le 1000$), and he wants to build a square barn on it. There are $t$ fruit trees on his farm ($1 \le t \le 10000$). To avoid cutting any trees, he wants to find an open area with no trees to build the barn. Your task is to compute and output the side length of the largest square barn that can be built on his farm without removing any trees. Of course, the sides of the barn must be parallel to the horizontal and vertical axes.

Consider the farm below, where '.' represents an empty cell and '#' represents a cell with a tree.

0 1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .

The largest barn has a side length of $5$ and can be placed at one of two positions in the lower-right corner.

Input Format

The first line contains two positive integers $n$ and $t$.

Lines $2$ through $t+1$ each contain two positive integers $x, y$ ($1 \le x, y \le n$).

Output Format

Output a single line: the maximum side length of John's barn.

8 3
2 2
2 6
6 3

5

Hint

Problem translation from NOCOW.

USACO Training Section 5.3.

Translated by ChatGPT 5