IATI | rectpoints

This was the problem page during the contest. Access the current page here.
Time limit: 0.4s
Memory limit: 256MB
Input:
Output:

Deni and Bob wonder how to spend the free time between their classes. They come up with the following. Deni marked NN points on a graph paper. It is possible that some of the points are marked on the same place but they are still counted as different points. The graph paper is rectangular in shape with width d1d_1 and height d2d_2, and on which the lower left vertex is assumed as a point with coordinates (0,0)(0, 0), and the upper right vertex - with coordinates (d1,d2)(d_1, d_2). Bob then came up with the numbers ww and hh, and together they began to search for a rectangle of width ww and height hh, with sides parallel to the sides of the graph paper and containing as many points as possible (including points on the sides of the sought rectangle). The big problem, however, was that they were not sure if they had found the maximum possible number of points that can be contained in such a rectangle. Deni knows that you are a very good programmer, so she asks you to write a program that for given NN points and sizes ww and hh for a rectangle, finds the maximum number of points that are contained in a rectangle of that size.

Input

From the first line of the standard input, your program reads three integers NN, ww and hh - the number of points marked on the graph paper and the sizes of the rectangle they are looking for. From each of the next NN lines, your program reads two integers xx and yy, separated by a space - the two coordinates of each of the marked points on the graph paper.

Output*

On a single line, your program prints an integer equal to the maximum number of points that can be contained in a rectangle with sizes ww and hh, which has sides parallel to the sides of the graph paper.

Constraints

  • 1N1051 ≤ N ≤ 10^5
  • 1x,y,w,h1081 ≤ x, y, w, h ≤ 10^8

Subtask 1 (0 points)

  • The second sample

Subtask 2 (11 points)

  • N102N ≤ 10^2
  • x,y,w,h102x, y, w, h ≤ 10^2

Subtask 3 (23 points)

  • N103N ≤ 10^3
  • x,y,w,h108x, y, w, h ≤ 10^8

Subtask 4 (12 points)

  • N105N ≤ 10^5
  • x,y,w,h103x, y, w, h ≤ 10^3
  • There is an optimal sought rectangle, for which one of the points is its upper right vertex

Subtask 5 (19 points)

  • N105N ≤ 10^5
  • x,y,w,h105x, y, w, h ≤ 10^5
  • There is an optimal sought rectangle, for which one of the points is its upper right vertex

Subtask 6 (26 points)

  • N105N ≤ 10^5
  • x,y,w,h105x, y, w, h ≤ 10^5

Subtask 7 (9 points)

  • N105N ≤ 10^5
  • x,y,w,h108x, y, w, h ≤ 10^8

Examples

stdin

6 2 3
1 1
3 1
2 2
3 3
5 3
3 5

stdout

4

Explanation

Аn optimal rectangle is the one with the upper right vertex at the point (3, 3). Its coordinates of the lower left vertex are (1, 0), of the lower right vertex - (3, 0) and of the upper left vertex - (1, 3). It contains the points (1, 1); (2, 2); (3, 1); (3, 3). Note that this example satisfies the additional constraints of the 4th and 5th subtasks.

stdin

10 8 8
8 9
20 14
3 9
7 8
3 4
7 8
10 19
6 11
5 10
8 2

stdout

7

Explanation

An optimal rectangle is the one with the upper right vertex at the point (9, 11) and it contains the points (8, 9); (3, 9); (7, 8); (3, 4); (7, 8); (6, 11) and (5, 10). Note that there is a repeating point (7, 8) and it is counted 2 times (as many times as it occurs). Unlike the previous example, there is no optimal solution in which one of the points is the upper right vertex of an optimal rectangle.

Contest info

Virtual contest

Start time: 1713245400000

Total duration: 5h0m0s

Status: Ended

Individual duration: 4h59m59s

Log in or sign up to be able to send submissions!