爆破目标

题目描述

有一个 $H \times W$ 格的二维网格。其中有 $M$ 个爆破目标,第 $i$ 个爆破目标的位置是 $\left(h_i, w_i \right)$。

高桥君选择一个格子放置炸弹并引爆。与炸弹同一行或同一列上的爆破目标会被炸毁。也可以把炸弹放置在存在爆破目标的格子上。

高桥君希望最大化被炸毁的爆破目标的数量。请回答最多能炸毁多少个爆破目标。

输入格式

输入按以下格式从标准输入给出:

$H$ $W$ $M$
$h_1$ $w_1$
$\vdots$
$h_M$ $w_M$

输出格式

输出答案。

样例

2 3 3
2 2
1 1
1 3

3

把炸弹放置在 $\left(1, 2\right)$,可以炸毁所有爆破目标。

3 3 4
3 3
3 1
1 1
1 2

3

5 5 10
2 5
4 3
2 3
5 5
2 2
5 4
5 3
5 1
3 5
1 4

6

数据范围

• 输入均为整数
• $1 \leq H, W \leq 3 \times 10^5$
• $1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)$
• $1 \leq h_i \leq H$
• $1 \leq w_i \leq W$
• $\left(h_i, w_i\right) \neq \left(h_j, w_j\right)$($i \neq j$)