← 返回题目列表

AtCoder · abc176_e

E. 轰炸机

中文机器翻译题面 查看原题

分数: 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