题目描述
有一个初始全零的矩阵 p,有 n 行 m 列。
给定正整数序列 a,b,长度分别为 x,y,且都严格递增。
你可以进行任意次操作,每次操作可以将某一行全部改为 a 中某个值,或将某一列全部改为 b 中某个值。
求若干次操作后,最大化矩阵中至少出现一次的所有不同数字之和。
换句话说,就是要求矩阵中所有出现过的数(相同的只算一次)之和最大是多少。
输入格式
第一行四个整数 n,m,x,y(1≤n,m≤105,1≤x,y≤n+m),分别表示矩阵的行数、列数以及两个数组的长度。
第二行给出 x 个整数 a1,a2,…,ax,满足
1≤a1<a2<⋯<ax≤n+m.
第三行给出 y 个整数 b1,b2,…,by,满足
1≤b1<b2<⋯<by≤n+m.
输出格式
输出一行一个整数,表示最终矩阵中,至少出现一次的所有不同数字之和的最大值。
样例 1 输入
1 3 3 3
1 2 3
1 2 3
样例 1 输出
6
样例 2 输入
7 2 9 1
1 2 3 4 5 6 7 8 9
9
样例 2 输出
44
数据范围
对于所有测试数据,保证:1≤n,m≤105,1≤x,y≤n+m,1≤ai,bi≤n+m,a 和 b 严格递增。
| 测试点 |
n,m≤ |
特殊性质 |
| 1∼4 |
5 |
无 |
| 5∼6 |
1000 |
m≤2 |
| 7∼8 |
无 |
| 9∼10 |
105 |
n>x,m>y |
| 11∼12 |
n>x 或 m>y |
| 13∼15 |
a 和 b 之间没有相同元素 |
| 16∼20 |
无 |