{"problem":{"name":"[JOI Open 2023] 花园 / Garden","description":{"content":"JOI 王国是一个神秘的王国，疆域辽阔无边。JOI 君是 JOI 国国王，他在计划分割疆域的一部分来建造他的花园。 JOI 网络可以考虑成一个充分大的二维网格，网格由从上到下和从左到右的正方形单元格密铺而成。有一个单元格是坐标原点。令 $(x,y)$ 表示表示从原点向右移动 $x$ 个单元格，再向上移动 $y$ 个单元格所到达的单元格。这里，向左移动 $a$ 个单元格意味着向右移动 $-a$ 个","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9514"},"statements":[{"statement_type":"Markdown","content":"JOI 王国是一个神秘的王国，疆域辽阔无边。JOI 君是 JOI 国国王，他在计划分割疆域的一部分来建造他的花园。\n\nJOI 网络可以考虑成一个充分大的二维网格，网格由从上到下和从左到右的正方形单元格密铺而成。有一个单元格是坐标原点。令 $(x,y)$ 表示表示从原点向右移动 $x$ 个单元格，再向上移动 $y$ 个单元格所到达的单元格。这里，向左移动 $a$ 个单元格意味着向右移动 $-a$ 个单元格。类似地，向下移动 $a$ 个单元格意味着向上移动 $-a$ 个单元格。\n\n在领土内有一些艺术品。这些艺术品根据放置在领土上的方式分为 **A 类**和 **B 类**。\n\n- 有 $N$ 种 A 类艺术品。第 $i$ 种艺术品（$1\\le i\\le N$）放在每个形如 $(P_i+kD,Q_i+lD)$ 的单元格上，其中 $k,l$ 为整数。\n- 有 $M$ 种 B 类艺术品。第 $j$ 种艺术品（$1\\le j\\le M$）放在每个形如 $(R_j+kD,y)$（其中 $k,y$ 为整数）或 $(x,S_j+lD)$（其中 $l,x$ 为整数）的单元格上。\n\n注意一个单元格中可能包含多种不同类别的艺术品。\n\nJOI 君计划在网格中选择一个矩形区域建造花园。换句话说，他会选择四个整数 $a,b,c,d$。然后形如 $(x,y)$ 的单元格将构成 JOI 君的花园，其中 $x,y$ 是满足 $a\\le x\\le b,c\\le y\\le d$ 的整数。因为 JOI 君喜欢看到多种艺术品，对于任意 $N+M$ 种艺术品中的一种，JOI 君的花园中需要至少包含这种艺术品中的一个。另一方面，如果 JOI 君计划要建的花园过大，JOI 国的居民就会生气。因此，JOI 君希望最小化花园包含的单元格数使得满足上述条件。\n\n给定艺术品的信息，写一个程序计算 JOI 君的花园所包含的最小单元格数。\n\n## Input\n\n第一行三个整数 $N,M,D$。\n\n接下来 $N$ 行，每行两个整数 $P_i,Q_i$。\n\n接下来 $M$ 行，每行两个整数 $R_j,S_j$。\n\n## Output\n\n输出一行一个整数，表示 JOI 君的花园所包含的最小单元格数。\n\n[samples]\n\n## Background\n\n**译自 [JOI Open 2023](https://contests.ioi-jp.org/open-2023/index.html) T3 「[庭園](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/garden/2023-open-garden-statement.pdf) / [Garden](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/garden/2023-open-garden-statement-en.pdf)」**\n\n## Note\n\n**【样例解释 #1】**\n\n下图展示了 JOI 国领土中的满足 $0\\le x<10,0\\le y<10$ 的单元格 $(x,y)$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/pnsc7qm4.png)\n\n在本图中，圆形和菱形分别表示 A 类和 B 类艺术品。圆形或菱形中的整数表示艺术品的种数。如果 JOI 君选择 $a=1,b=2,c=2,d=5$，JOI 君的花园就是黑色矩形区域。这种情况下，对于这三种艺术品，JOI 君的花园中至少会有每种中的一个。花园所占单元格数为 $8$。因为没有比这个花园占地更小且满足条件的花园了，因此输出 $8$。\n\n这组样例满足所有子任务的限制。\n\n**【样例解释 #2】**\n\n这组样例满足子任务 $1,4,5,6$ 的限制。\n\n**【样例解释 #3】**\n\n这组样例满足子任务 $1,5,6$ 的限制。\n\n**【数据范围】**\n\n对于所有数据，满足：\n\n- $N,M\\ge 1$\n- $N+M\\le 5\\times 10^5$\n- $1\\le D\\le 5\\ 000$\n- $0\\le P_i,Q_i,R_j,S_j<D$\n\n详细子任务附加限制及分值如下表所示。\n\n| 子任务 |        附加限制        | 分值 |\n| :----: | :--------------------: | :--: |\n|  $1$   |        $M\\le 8$        | $15$ |\n|  $2$   | $D\\le 10,N+M\\le 5000$  | $6$  |\n|  $3$   | $D\\le 50,N+M\\le 5000$  | $8$  |\n|  $4$   | $D\\le 100,N+M\\le 5000$ | $16$ |\n|  $5$   |     $N+M\\le 5000$      | $30$ |\n|  $6$   |       无附加限制       | $25$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9514","tags":["2023","O2优化","JOI（日本）"],"sample_group":[["2 1 5\n1 4\n2 2\n0 0\n","8\n"],["3 4 100\n20 26\n81 56\n20 3\n58 71\n74 82\n95 61\n95 61\n","2840\n"],["5 7 5000\n1046 365\n4122 1166\n4009 2896\n1815 4065\n4372 1651\n2382 123\n1475 836\n3313 4005\n2579 568\n4300 4867\n1050 3214\n3589 4653\n","10543092\n"]],"created_at":"2026-03-03 11:09:25"}}