Square Fishing Net

Interview

Time limit1sMemory limit1024 MB

Summary

Given n fish points and a net side length s, find the most fish that one axis-aligned square of side s can cover, boundary included.

Level: Easy3 of 10
Topics: Brute force, Implementation
Solved: No attempts yet

Problem

With so many activities and events held online these days, we are going on a virtual fishing trip!

Given the coordinates $(x,y)$ of $n$ points (each point is a fish) and a square (the fishing net), what is the maximum number of fish you can catch with one try? You can place the net anywhere, but its sides must be parallel to the X-axis and the Y-axis. A fish is caught if it is inside or on the boundary of the net.

Input

The first line contains two integers $s$ and $n$ . Here $s$ ( $1 \le s \le 100$ ) is the length of one side of the net, and $n$ ( $1 \le n \le 100$ ) is the number of fish. Each of the next $n$ lines contains the integer coordinates $(x,y)$ of one fish, each between 1 and 100 inclusive. No two fish are at the same location.

Output

Print the maximum number of fish you can catch.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
50 2
10 5
11 5
```
Expected output
```
2
```