← 返回题目列表

AtCoder · abc023_c

C. 收藏王

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

問題文

高桥正计划搬到某个房间。

房间在垂直方向上有方形单元格。 R 线,水平 C 它们按行排列。其中 i (1 ≦ i ≦ R) 线 j (1 ≦ j ≦ C) 标记列中的方块。 我们称之为 (i,j) 。

这些方格共有糖果 N 存在。糖果用 糖果的编号最大为 1 到 N 。 i (1 ≦ i ≦ N) 是质量 它位于 (r_i,c_i) 。其中哪一个 2 没有两颗糖果位于同一个方块上。

高桥可以选择任何一个方格。 1 移动到方块。移动后,高桥获得如下所示的糖果。

  • 首先,获取与高桥所在方格同一行的所有方格中的所有糖果。
  • 接下来,对于与高桥所在方格同一行的所有方格,获取该方格中的所有糖果。

高桥君除了这个动作不会做任何事。

高桥有适量的糖果可供获取。 我想要 K 件。求出可被视为此类移动目的地的方格总数。


入力

输入将以以下形式从标准输入给出。

R C K
N
r_1 c_1
r_2 c_2
:
r_N c_N
  • 1 行中,3 整数 R (1 ≦ R ≦ 100,000), C (1 ≦ C ≦ 100,000), K (1 ≦ K ≦ 100,000) 用空格分隔。这意味着组成房间的方形单元是垂直的。 R 行、横 C 表示有一个列。K 是高桥想要获得的糖果数量。
  • 2 行包含一个表示糖果数量的整数。 N (K ≦ N ≦ 100,000) 被给予。
  • 3 从行 N 行提供有关糖果的信息。N 行数过多 在 i (1 ≦ i ≦ N) 行中,2 整数 r_i (1 ≦ r_i ≦ R), c_i (1 ≦ c_i ≦ C) 用空格分隔。这是糖果 i 是一个正方形 (r_i,c_i)。
  • i≠j 时, 当您移动到(r_i,c_i)≠(r_j,c_j) 变为。

部分点

针对此问题设置了部分分数。 满足

  • R ≦ 50 和 如果您对 C ≦ 50 和 如果您对 N ≦ 50 的数据集 如果您正确回答 1 , 给出30 点。
  • 没有附加约束的数据集 如果您正确回答 2 的回答正确,除上述之外, 70 点。

出力

获得的糖果数量正好是 计算目的地总数,使得 K 目的地总数 1 行输出。还在输出末尾添加换行符。


入力例1

3 5 3
5
1 2
2 1
2 5
3 2
3 5

出力例1

5

例如,质量 考虑高桥移动到 (3,2) 的情况。

  • 飴 1 是 它位于 (1,2) 。这个正方形是正方形 由于与 (3,2) 在同一行,高桥可以购买糖果。 获取 1 。
  • 飴 2 是 它位于 (2,1) 。这个正方形是正方形 由于与 (3,2) 不在同一行或同一列,因此高桥是 您不会得到 2 。 由于它与
  • 飴 3 是 它位于 (2,5) 。这个正方形是正方形 由于与 (3,2) 不在同一行或同一列,因此高桥是 您不会得到 3 。 由于它与
  • 飴 4 是 它位于 (3,2) 。这个正方形是正方形 由于与 (3,2) 在同一个方格(同行同列),所以高桥可以吃掉糖果。 由于与 4 。
  • 飴 5 是 它位于 (3,5) 。这个正方形是正方形 由于与 (3,2) 在同一行,所以高桥是糖果。 5 。

从上面看,糖果 1, 4, 5 只是 3 由于你只得到 1 颗糖果, (3,2) 是您获得的糖果的确切数量。 K 目的地。

其他质量 (1,5), (2,5), (3,1), (3,5) 满足条件,所以答案是 输出 5 。


入力例2

7 3 1
4
3 2
3 3
4 2
4 3

出力例2

0

无论你如何指定目的地,获得的糖果数量都必须准确 1 不能。


入力例3

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

出力例3

20