序列粘贴 - 代码源竞赛平台

题目描述

蜗蜗正在使用一个序列编辑器。剪贴板中保存着长度为 $n$ 的整数序列 $a$，编辑区中的序列 $c$ 初始为空。他希望把编辑区中的序列变成给定的、长度为 $m$ 的目标序列 $b$。

蜗蜗可以执行任意次以下操作：

• 粘贴：花费 $x$，将完整的序列 $a$ 按原顺序追加到序列 $c$ 的末尾；
• 修改：花费 $y$，将序列 $c$ 中的一个元素加 $1$ 或减 $1$；
• 删除：花费 $z$，删除序列 $c$ 中的一个元素，其他元素的相对顺序保持不变。

修改和删除只影响编辑区，不会改变剪贴板中的序列 $a$。每次粘贴的都是原来的序列 $a$。

请你求出使序列 $c$ 与目标序列 $b$ 完全相同所需的最小总费用。

输入格式

第一行包含一个整数 $T$，表示测试用例数量。

对于每组测试用例：

• 第一行包含五个整数 $n,m,x,y,z$，分别表示两个序列的长度以及粘贴、修改、删除操作的费用；
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示剪贴板中的序列；
• 第三行包含 $m$ 个整数 $b_1,b_2,\ldots,b_m$，表示目标序列。

输出格式

对于每组测试用例，输出一行一个整数，表示得到目标序列所需的最小总费用。

样例

2
3 2 4 10 3
1 5 9
1 9
2 2 1 100 0
0 100
100 0

7
2

样例解释

第一组测试用例中，粘贴一次得到序列 $[1,5,9]$，再删除中间的 $5$，即可得到目标序列 $[1,9]$，总费用为 $4+3=7$。

第二组测试用例中，粘贴两次得到序列 $[0,100,0,100]$，再删除第一个和最后一个元素，即可得到目标序列 $[100,0]$。删除操作的费用为 $0$，因此总费用为 $1+1=2$。

数据范围

对于 100% 的数据，保证 $1\le T\le 10^4$，$1\le n,m\le 3000$，$0\le x,y,z\le 10^6$，$0\le a_i,b_i\le 10^9$。

对于同一个输入文件中的所有测试用例，保证 $\sum nm\le 9\times 10^6$，$\sum(n+m)\le 2\times 10^5$。