Problem Description

Bitaro, who loves fruits, decided to challenge himself to a strawberry picking game. In front of Bitaro, there is a table with a rectangular shape divided into a grid of $H$ rows and $W$ columns. There are $N$ strawberries placed on the table, and the $i$-th ($1 \leq i \leq N$) strawberry is located in the cell at the $A_i$-th row from the top and the $B_i$-th column from the left. It is possible that multiple strawberries are placed in the same cell.

Bitaro will choose a square region of $3$ rows and $3$ columns, consisting of $9$ cells, and pick all the strawberries in those cells. This action is performed only once.

Bitaro wants to pick as many strawberries as possible.

Given the size of the table and the positions of the strawberries, create a program to find the maximum number of strawberries that can be picked.

Input Format

The input is given from the standard input in the following format:

$H$ $W$ $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

Output Format

Output the maximum number of strawberries that can be picked in one line to the standard output.

Sample Input and Output

Sample Input #1

4 5
7
1 1
1 5
2 2
2 4
3 3
4 2
4 4

Sample Output #1

5

Sample Input #2

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

Sample Output #2

4

Sample Input #3

3 99999
9
1 77813
2 77813
3 77813
1 77814
2 77814
3 77814
1 77815
2 77815
3 77815

Sample Output #3

9

Sample Input #4

11 11
20
7 7
6 11
5 7
8 8
9 9
5 5
8 4
4 4
4 8
2 6
1 6
6 2
3 3
9 3
7 5
6 1
10 6
6 10
11 6
3 9

Sample Output #4

4

Notes/Hints

Constraints

• $3 \leq H \leq 1,000,000,000$.
• $3 \leq W \leq 1,000,000,000$.
• $1 \leq N \leq 60,000$.
• $1 \leq A_i \leq H$ ($1 \leq i \leq N$).
• $1 \leq B_i \leq W$ ($1 \leq i \leq N$).
• All input values are integers.

Subtasks

1. ($14$ points) $H \leq 1,000$, $W \leq 1,000$, $N \leq 20$.
2. ($16$ points) $H \leq 1,000$, $W \leq 1,000$.
3. ($29$ points) $H \leq 1,000,000$, $N \leq 500$.
4. ($15$ points) $H = 3$.
5. ($20$ points) $H \leq 1,000,000$.
6. ($6$ points) No additional constraints.

Grading Notes

All submissions are graded on the judge system.

A submitted source code is considered correct for a subtask if it returns the correct result for all test input data corresponding to that subtask.

The score for each submission is the sum of the scores of the subtasks that the submitted source code is considered correct for.

The score for this task is the maximum score of all submissions for this task.

The current score can be checked from the "My Score Status" tab in the "Submission Results".

Sample Explanation 1

The arrangement of strawberries is as shown in the figure (red circles represent strawberries). By choosing the cells in the region outlined with a thick frame, $5$ strawberries can be picked. It is not possible to pick more than $5$ strawberries, so output $5$. This input example satisfies the constraints of subtasks $1, 2, 3, 5, 6$.

Sample Explanation 2

It is possible that multiple strawberries are placed in the same cell. This input example satisfies the constraints of all subtasks.

Sample Explanation 3

This input example satisfies the constraints of subtasks $3, 4, 5, 6$.

Sample Explanation 4

This input example satisfies the constraints of subtasks $1, 2, 3, 5, 6$.

见题面 Input 部分

见题面 Output 部分