3907 - 宝藏

题目描述

在一座古城中,有一个 N \times M 的矩形藏宝箱,宝箱由 N \times M 个方格组成,其中隐藏着 K 个的宝藏。

每个宝藏的位置由坐标 (X_i, Y_i) 确定,即:宝藏位于该矩阵的第 X_i 行、第 Y_i 列的方格中。

寻宝人需在矩阵中任意选择一个方格,并在那里激活一个古老的机关。这个机关会影响其所在行和列中的所有宝藏,将封印它们的容器打开。

寻宝人的目标是获得尽可能多的宝藏。请编程计算出,寻宝人最多能获得的宝藏数量。

输入

第一行读入三个整数,表示 N,M,K

接下来读入 K 行,每行包含两个整数 X_i, Y_i,表示宝藏的位置。

输出

输出寻宝人最多能获得的宝藏数量。

样例

输入

2 3 3
2 2
1 1
1 3

输出

3

输入

3 3 4
3 3
3 1
1 1
1 2

输出

3

输入

8 195 57
3 6
3 155
3 47
2 87
2 193
5 132
2 92
1 150
3 182
4 147
2 53
2 138
3 131
6 72
4 182
7 68
5 179
8 65
5 2
5 124
2 108
3 111
3 165
2 2
3 56
1 61
5 76
6 178
5 116
6 156
5 91
3 78
1 174
4 117
3 34
5 40
8 86
6 82
6 24
1 153
1 1
2 146
1 164
6 185
5 101
6 191
8 145
8 59
8 69
8 168
6 147
4 62
6 165
8 105
8 72
1 168
4 36

输出

12
说明

样例 1 解释

我们可以通过激活 (1, 2) 方格中的机关,获取 3 个宝藏。

数据范围

对于 40\% 的数据,满足 1 \leq N,M \leq 200

对于 100\% 的数据,满足 1 \leq N, M \leq 3 \times 10^51 \leq K \leq \min(N \times M, 3 \times 10^5)1 \leq X_i \leq N1 \leq Y_i \leq M(X_i, Y_i) \neq (X_j, Y_j)i \neq j)。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题