[R35D]合并数组 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定三个整数数组：长度为 $n$ 的数组 $a$，长度为 $m$ 的数组 $b$，以及长度为 $n+m$ 的数组 $c$。

你需要通过合并数组 $a$ 和 $b$ 来构造一个新的数组 $d$，其长度为 $n+m$。合并规则如下：

1. 数组 $d$ 包含了数组 $a$ 和 $b$ 中的所有元素，每个元素恰好出现一次。
2. 在数组 $d$ 中，原来属于数组 $a$ 的元素之间的相对顺序必须保持不变。
3. 同样，在数组 $d$ 中，原来属于数组 $b$ 的元素之间的相对顺序也必须保持不变。

你的任务是找到一个最优的合并方案，使得价值 $\sum_{i=1}^{n+m} d_i \times c_i$ 最大。请你输出这个最大的价值。

格式

输入格式

第一行包含两个整数 $n, m$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组 $a$ 的值。

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$，表示数组 $b$ 的值。

第四行包含 $n+m$ 个整数 $c_1, c_2, \dots, c_{n+m}$，表示数组 $c$ 的值。

输出格式

输出一行，一个整数，表示可以得到的最大价值。

样例

样例输入 #1

2 1
20 10
30
1 5 2

样例输出 #1

190

样例解释 #1

满足条件的让价值最大的 $d$ 数组为 $[\red{20} , \blue{30} , \red{10}]$，其中红色的数字表示其来自数组 $a$，蓝色的数字表示其来自数组 $b$。最大价值为 $20 \times 1 + 30 \times 5 + 10 \times 2 = 20 + 150 + 20 = 190$。

数据规模

对于 $40 \%$ 的数据，$1 \leq n , m \leq 10$。

对于 $100\%$ 的数据，$1 \le n, m \le 2000$，$1 \le a_i, b_i, c_i \le 10^6$。