This page is still under construction.

Parts of this page are still being built. What you see may change.

Goldmine

Time limit3sMemory limit512 MB

Summary
Given n points and an axis-aligned rectangle of fixed width s and height w, find the maximum number of points the rectangle can cover, borders included.
Level

Medium7 of 10

Topics
Sorting, Two pointers, Sliding window, Prefix sum
Solved
No attempts yet

Problem

Byteman, one of the longest-serving and most devoted employees of the Goldmine of Byteland, is about to retire at the end of the year. The mine's management would like to reward him for his conscientious work. As a reward, Byteman may receive a small lot: a rectangular part of the mine whose two sides have lengths ss and ww and are parallel to the coordinate axes. He may choose where to place the lot.

The value of a lot depends on where it is placed. The value of a lot is the number of gold nuggets inside it. A nugget lying exactly on the border of the lot still counts as being inside it.

Your task is to write a program that computes the maximum possible value of the lot, that is, its value at the best location. To simplify the problem, assume that the terrain of the mine is unbounded, while the region where nuggets occur is finite.

Write a program that:

  • reads the positions of the gold nuggets from standard input,
  • computes the maximum value of a lot (the maximum number of nuggets that a lot of the given size can contain),
  • writes the result to standard output.

Input

The first line contains two positive integers ss and ww separated by a single space (1≤s,w≤10 0001 \le s, w \le 10\,000). They are the lengths of the lot's sides parallel to the OX axis and the OY axis, respectively.

The second line contains one positive integer nn, the number of nuggets in the mine (1≤n≤15 0001 \le n \le 15\,000).

Each of the next nn lines contains the coordinates of one nugget: two integers xx and yy separated by a single space (−30 000≤x,y≤30 000-30\,000 \le x, y \le 30\,000), giving the xx-coordinate and the yy-coordinate of that nugget.

Output

Print a single integer equal to the value of the most valuable lot of the given size.

Examples1

  1. Example 1

    Input
    1 2
    12
    0 0
    1 1
    2 2
    3 3
    4 5
    5 5
    4 2
    1 4
    0 5
    5 0
    2 3
    3 2
    
    Expected output
    4