P8370 [POI 2001 R3] Goldmine

As one of the most meritorious employees of $\text{The Goldmine}$ in $\text{Byteland}$, $\text{Byteman}$ is going to retire at the end of the year. To recognize his diligent work, the management of $\text{The Goldmine}$ is willing to reward him with a small rectangular mining plot. The side lengths of this plot are $s$ and $w$, and its sides are parallel to the axes of the coordinate system. He can choose the position of the rectangle himself. Of course, the value of the plot depends on its position. Its value is defined as the number of natural gold ores within this area (if an ore lies on the boundary of the plot, it is also considered to be inside the area). Your task is to compute the maximum possible value of such a plot (i.e., choose the best position for it). For simplicity, assume that the entire mining area is infinite, but the region containing natural gold ores is finite. Write a program that: 1. Reads the positions of the natural gold ores. 2. Computes the maximum possible value of this plot (i.e., the maximum number of natural gold ores contained in a rectangle of the given size).

The first line contains two positive integers $s, w$, representing the lengths of the sides of the rectangle parallel to the $X$ axis and the $Y$ axis, respectively. The second line contains a positive integer $n$, which denotes the number of natural ores in this goldmine area. The next $n$ lines each contain two integers $x, y$ separated by a single space, representing the $X$ coordinate and the $Y$ coordinate of a natural gold ore.

Output one integer, representing the maximum value of a mining plot of the given size.

For $100\%$ of the data: $1 \le s, w \le 10000, 1 \le n \le 15000, -30000 \le x, y \le 30000$. Translated by ChatGPT 5