在一座古城中,有一个 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, 2) 方格中的机关,获取 3 个宝藏。
对于 40\% 的数据,满足 1 \leq N,M \leq 200。
对于 100\% 的数据,满足 1 \leq N, M \leq 3 \times 10^5,1 \leq K \leq \min(N \times M, 3 \times 10^5),1 \leq X_i \leq N,1 \leq Y_i \leq M,(X_i, Y_i) \neq (X_j, Y_j)(i \neq j)。