鼠标输入密码 - 代码源竞赛平台

题目描述

蜗蜗想用鼠标输入一个密码。密码是长度为 $m$ 的整数序列 $b$，而剪贴板里保存着长度为 $n$ 的整数序列 $a$。屏幕上的编辑区序列 $c$ 起初为空。

他可以使用以下三种操作，次数不限：

• 粘贴：支付 $x$，把剪贴板中完整的序列 $a$ 按原顺序追加到 $c$ 的末尾；
• 滚动：支付 $y$，把 $c$ 中的一个元素增加 $1$ 或减少 $1$；
• 删除：支付 $z$，从 $c$ 中删除一个元素，其余元素的相对顺序保持不变。

滚动和删除只改变编辑区，不会改变剪贴板；以后每次粘贴得到的仍是原来的序列 $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$。

输出格式

对于每组测试用例，输出一行一个整数，表示输入密码所需的最小总费用。

样例

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

11
12
3

2
1 3 0 0 0
1
100 200 300
1 2 5 1 0
3
2 4

0
12

样例解释

样例 1 的第一组数据中，粘贴两次得到 $[1,10,1,10]$，再删除最后一个元素，总费用为 $2\times4+3=11$。第二组数据中，粘贴一次后将 $2$ 增加到 $4$，再删除 $9$，总费用为 $3+2\times2+5=12$。第三组数据中，粘贴一次并删除中间的 $99$，总费用为 $2+1=3$。

样例 2 的第一组数据中，三种操作均不收费，答案为 $0$。第二组数据中，可以粘贴两次，将 $[3,3]$ 中两个元素分别改为 $2$ 和 $4$，总费用为 $2\times5+2\times1=12$。

数据范围

对于 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$。