分数: 500 点
问题陈述
我们有一个二维网格 H \times W 方块。有 M 在此网格中要摧毁的目标 - 的位置 i- 第一个目标是 \left(h_i, w_i \right).
高桥会在这个网格中选择一个方格,在那里放置一枚炸弹,然后点燃它。炸弹将摧毁放置炸弹的行或列中的所有目标。可以将炸弹放置在有目标的正方形上。
高桥正试图最大限度地增加要摧毁的目标数量。找出可以摧毁的最大目标数量。
约束
- 输入中的所有值都是整数。
- 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) \left(i \neq j\right)
输入
输入由标准输入按以下格式给出:
H W M h_1 w_1 \vdots h_M w_M
输出
打印答案。
示例输入 1
2 3 3 2 2 1 1 1 3
示例输出 1
3
我们可以通过将炸弹放置在 \left(1, 2\right).
示例输入 2
3 3 4 3 3 3 1 1 1 1 2
示例输出 2
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