Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM-ICPC亚洲区预选赛(北京赛区)游戏对抗邀请赛​正在报名中

Language:
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1165 Accepted: 301

Description

In his fabulous trip to El Dorado, Kamran made his fortune. After helping the king solve a difficult math problem, the king granted a piece of royal garden to Kamran. The king wrote a letter to the gardener, so that a rectangular region of the royal garden with a specified area, be given to Kamran. You could guess that the trees in El Dorado are made from Gold!

After taking the letter to the royal gardener, Kamran found out that, unfortunately, there is no specific pattern for the location of the trees in the garden. To get the most profit, Kamran talked to the gardener and convinced him that it would not matter much, if Kamran chose the location of his rectangular share, and if he would choose a share smaller than the letter suggests. However, the gardener insisted that Kamran’s subgarden should have sides parallel to the garden sides (which is itself a rectangle), and that vertices should have integer coordinates. The area of the piece of land must be positive, so that the king would not suspect anything.

Now, given the locations of the trees in the garden and the maximum allowed area of his share, Kamran should find a rectangular sub-garden with maximum number of trees inside; if a tree is on the border of the sub-garden, he can safely claim it.

Input

The only number of the first line, T, is the number of different instances to be solved. T blocks follow, which describe different independent problems.

The first line of a block, contains two integers 0 ≤ F ≤ 1000, the number of trees in the field, and the specified area A. The following F lines, each describes the location of a tree, by two nonnegative integers x, y (1 ≤ x, y ≤ 1000). No two trees have the same position.

Output

For each block in the input, write a single integer, which is the maximum number of trees that Kamran can obtain.

Sample Input

```1
3 3
1 1
1 3
1 5```

Sample Output

`2`

Source

[Submit]   [Go Back]   [Status]   [Discuss]