Grandpa's Other Estate

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 100 points and a square side length r, place the axis-aligned square to cover as many points as possible, counting border points as inside.

Level: Medium4 of 10
Topics: Array, Sorting, Two pointers, Brute force
Solved: No attempts yet

Problem

Kamran inherited many of his grandpa's belongings. His grandpa was a mathematician who loved puzzles, and he left Kamran one more problem to solve.

Grandpa owned a large garden full of valuable walnut trees. His will states that Kamran may inherit one square-shaped piece of land of a given side length, with its sides parallel to the $x$ - and $y$ -axes. Since the will places no other restriction, Kamran wants to position this square so that it contains as many trees as possible.

Treat each tree as a point in the plane and the land as an axis-aligned square. Find a position for the square that encloses the maximum number of trees. A tree lying exactly on the border of the square is considered to be inside it.

Input

The first line contains an integer $t$ ( $1 \le t \le 10$ ), the number of test cases.

Each test case begins with a line containing two integers $n$ ( $1 \le n \le 100$ ), the number of trees, and $r$ ( $1 \le r \le 1000$ ), the side length of the land. The next $n$ lines each contain two integers $x$ and $y$ ( $0 \le x, y \le 100\,000$ ), the coordinates of a walnut tree. All tree coordinates are pairwise distinct.

Output

For each test case, print a single line containing the maximum number of trees that Kamran can enclose in the square.

Examples3

Example 1
Input
```
1
3 1
1 2
2 1
4 3
```
Expected output
```
2
```
Example 2
Input
```
1
4 10
0 0
1 1
2 2
10 10
```
Expected output
```
4
```

Example 3

Input

3
3 1
1 2
2 1
4 3
1 1000
50000 50000
4 10
0 0
1 1
2 2
10 10

Expected output

2
1
4