AT_abc176_e [ABC176E] Bomber

题目描述

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

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

高桥君想要最大化被炸毁的爆破目标数量。请问最多可以炸毁多少个爆破目标？

输入格式

输入通过标准输入按以下格式给出。

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2 3 3
2 2
1 1
1 3

输出 #1

3

输入输出样例 #2

输入 #2

3 3 4
3 3
3 1
1 1
1 2

输出 #2

3

输入输出样例 #3

输入 #3

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

输出 #3

6

说明/提示

限制条件

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

样例解释 1

将炸弹放在 $(1, 2)$ 处，可以炸毁所有爆破目标。

由 ChatGPT 4.1 翻译