Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Fortune at El Dorado
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1160Accepted: 299

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]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator