4088 - 灯光规划

题目描述

一座城市正在规划夜间的灯光布局。城市的地图被划分为一个由 N 条横街和 M 条纵巷组成的网格,每个交叉点是一个需要考虑是否点亮的灯位。规划团队决定通过以下步骤点亮部分灯位:

  • 第一步:选择 X 条横街,将这些横街上的所有灯位点亮。

  • 第二步:选择 Y 条纵巷,将这些纵巷上的所有灯位点亮。

一个灯位只要被横街或纵巷的任一选择覆盖,就会被点亮。规划完成后,团队需要统计有多少个灯位仍然未被点亮,以便后续调整方案。

例如,假设城市地图有 3 条横街和 5 条纵巷,团队先选择了第 1 条和第 3 条横街点亮,再选择了第 1 条、第 3 条和第 5 条纵巷点亮,最终有 2 个灯位未被点亮。

下图展示了上述例子的亮灯效果,被点亮灯位用 ★ 表示,没有被点亮的灯位用 ○ 表示。

纵巷1纵巷2纵巷3纵巷4纵巷5
横街1
横街2
横街3

你的任务是根据给定的横街和纵巷选择方案,计算未被点亮的灯位数量。

输入

第一行包含 4 个整数 NMXY,分别表示横街数量、纵巷数量、被选择的横街数量和被选择的纵巷数量,整数之间用一个空格隔开。

第二行包含 X不同的整数,表示被选择的横街编号,整数之间用一个空格隔开。

第三行包含 Y不同的整数,表示被选择的纵巷编号,整数之间用一个空格隔开。

输出

输出一个整数,表示未被点亮的灯位数量。

样例

输入

3 5 2 3
1 3
1 3 5

输出

2

输入

10 20 5 8
10 2 4 1 3 
5 19 11 7 14 10 4 16 

输出

60

输入

16 27 6 15
5 2 15 11 8 13
16 15 17 25 1 12 22 10 21 9 20 5 27 19 18

输出

120
说明

样例 1 说明

样例 1 请参考题目中给出的示意图。

数据范围

对于 60\% 的数据,满足 1 \leq X \leq N \leq 10^31 \leq Y \leq M \leq 10^3

对于 100\% 的数据,满足 1 \leq X \leq N \leq 10^51 \leq Y \leq M \leq 10^5X 个横街编号互不相同且在 [1, N] 的范围内,Y 个纵巷编号互不相同且在 [1, M] 的范围内。

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


上一题 下一题