Codah ClubGyakorolj. Küldd be. Fejlődj.
Bejelentkezés
Magyar
#000006

bogatas

Shumadija (a Serbian province) was once full of forests, but it can't be proud of them anymore. A huge effort is being made to prevent trees from being unnecessarily cut down. A local newcomer, who is also a very rich man, bought a relatively large piece of land (square-shaped), and he wants to build a house on it. He also wants to make the house as large as possible and and square-shaped with its sides parallel to the sides of the land that the house will be built on.


The land is divided into little 1x1 squares. One tree occupies exactly one square. Since the land is big, it's very hard to find the largest square with its sides parallel to the sides of the land and with no trees on it. For a given map of the land that describes the position of all the trees, you must find the square with the largest sides and with no trees on it. The length of the square's side is the number of 1x1 squares along its side.


InputThe input is read from the standard input. The first line of input contains a number N ( N <= 200) that tells the length of the land's sides. In the next line there will be a number P , which is the number of trees positioned on this land. The next P lines contain two numbers that represent the coordinates of a tree.

OutputOne and only line of the standard output should have only one number, which tells the length of the side of the largest square with no trees in it.

Input:
5
3
2 2
4 2
4 4
Output:
3
Explanation:
Coordinates of upper-left point of square are (1,3) and lower-right (3,5).

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.