問題文
高桥正计划搬到某个房间。
房间在垂直方向上有方形单元格。 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