Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Fortune at El Dorado
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1161Accepted: 300


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.


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.


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

Sample Input

3 3
1 1
1 3
1 5

Sample Output



[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