题目描述
有一组按键,每个按键可以输入若干种不同的字符,字符共有 m 种。
对于第 i 个按键,将它所对应的字符按顺序排列为
wi,1,wi,2,…,wi,ci
每个字符恰好仅可以由一个键打出。
按键始终有一个当前选中的字符,记其下标为 ki。初始状态下,所有按键的 ki 都为 1。
输入当前选中的字符时,只需普通按键,耗时 p。
如果要输入同一按键上的第 j 个字符,则需要长按,耗时为
q+∣j−ki∣
注意,这里并不保证 q>p。
此外,还可以使用一种全局切换操作。每次切换都会让所有按键的当前字符同时向后移动一位:
ki←kimodci+1.
执行一次切换需要耗时 t。切换可以进行任意次,也可以完全不使用。
现在给定一串需要按顺序输入的字符。请合理安排输入方式以及全局切换的时机,使输入整个序列的总耗时最小。
输入格式
第一行包含五个正整数 n,m,p,q,t,分别表示按键数量、字符总数、普通输入当前字符的耗时、长按的基础耗时以及全局切换一次的耗时。
接下来有 n 行描述各个按键。
第 i 行包含一个整数 ci,随后给出 ci 个整数
wi,1,wi,2,…,wi,ci,
表示该按键能够输入的全部字符。
所有字符恰好对应一个按键。
随后一行包含一个整数 L,表示待输入序列的长度。
最后一行给出 L 个整数
s1,s2,…,sL,
表示需要按顺序输入的字符。
输出格式
输出一个整数,表示完成整个字符序列所需的最小总耗时。
样例 1 输入
2 5 3 7 2
2 1 3
3 2 4 5
6
1 3 4 5 2 3
样例 1 输出
24
样例 2 输入
2 7 2 20 1
5 3 1 5 7 2
2 4 6
8
3 6 7 4 2 1 5 3
样例 2 输出
26
数据范围
对于所有测试数据,保证 1≤n,m≤5000,1≤ci≤5,1≤wi,j,si≤m,1≤L≤105,1≤p,q,t≤2×104。
保证 1∼m 在 w 的输入中均出现且只出现一次。
| 测试点 |
n≤ |
特殊性质 |
| 1∼4 |
5 |
无 |
| 5∼7 |
100 |
| 8∼9 |
5000 |
ci=1 |
| 10 |
L=1 |
| 11∼14 |
所有的 ci 都相等 |
| 15 |
所有 si 都相等 |
| 16∼20 |
无 |