#CW3. 矩阵赋值(matrix)

矩阵赋值(matrix)

题目描述

有一个初始全零的矩阵 pp,有 nn 行 mm 列。

给定正整数序列 a,ba, b,长度分别为 x,yx, y,且都严格递增。

你可以进行任意次操作,每次操作可以将某一行全部改为 aa 中某个值,或将某一列全部改为 bb 中某个值。

求若干次操作后,最大化矩阵中至少出现一次的所有不同数字之和。

换句话说,就是要求矩阵中所有出现过的数(相同的只算一次)之和最大是多少。

输入格式

第一行四个整数 n,m,x,yn, m, x, y(1≤n,m≤1051 \le n, m \le 10^5,1≤x,y≤n+m1 \le x, y \le n + m),分别表示矩阵的行数、列数以及两个数组的长度。

第二行给出 xx 个整数 a1,a2,…,axa_1, a_2, \ldots, a_x,满足

1≤a1<a2<⋯<ax≤n+m.1 \le a_1 < a_2 < \cdots < a_x \le n + m.

第三行给出 yy 个整数 b1,b2,…,byb_1, b_2, \ldots, b_y,满足

1≤b1<b2<⋯<by≤n+m.1 \le b_1 < b_2 < \cdots < b_y \le 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≤1051 \le n, m \le 10^5,1≤x,y≤n+m1 \le x, y \le n + m,1≤ai,bi≤n+m1 \le a_i, b_i \le n + m,aa 和 bb 严格递增。

测试点 n,m≤n, m \le 特殊性质
1∼41 \sim 4 55 无
5∼65 \sim 6 10001000 m≤2m \le 2
7∼87 \sim 8 无
9∼109 \sim 10 10510^5 n>xn > x,m>ym > y
11∼1211 \sim 12 n>xn > x 或 m>ym > y
13∼1513 \sim 15 aa 和 bb 之间没有相同元素
16∼2016 \sim 20 无