Minimum Square Corral

Farmer John wishes to build a corral for his cows. The cows are picky: the corral must be a square with its sides parallel to the X and Y axes, and it must contain at least C clover fields. Each clover field occupies a 1×1 block whose lower‐left corner is at integer coordinates between 1 and 10,000. Note that more than one clover field might occur at the same location.

A clover field is considered inside the corral if the entire 1×1 block is contained within the corral. In other words, if the square corral has lower left corner (X, Y) and side length L, then a clover field at (x,y) is contained if and only if

$$X \le x \le X+L-1 \quad\text{and}\quad Y \le y \le Y+L-1. $$

Your task is to help Farmer John determine the smallest possible side length L of a square corral that contains at least C clover fields.

Constraints: \(1\le C\le N\le 500\).

inputFormat

The first line contains two integers: C and N, where C is the minimum number of clover fields required and N is the total number of clover fields on the farm.

Each of the next N lines contains two integers representing the x and y coordinates of a clover field. Note that the same coordinate pair may appear multiple times if more than one clover field grows in that 1×1 area.

outputFormat

Output a single integer: the minimum side length L of a square corral (with edges parallel to the axes) that contains at least C clover fields. Remember that a clover field at (x, y) is fully contained only if it fits inside [X, X+L] in the x-direction and [Y, Y+L] in the y-direction, which requires x \(\le\) X+L-1 and y \(\le\) Y+L-1.

sample

3 5
1 1
2 2
3 3
4 4
5 5

3