#CW6. 键位轮转(keyboard)

键位轮转(keyboard)

题目描述

有一组按键,每个按键可以输入若干种不同的字符,字符共有 mm 种。

对于第 ii 个按键,将它所对应的字符按顺序排列为

wi,1,wi,2,…,wi,ciw_{i,1}, w_{i,2}, \ldots, w_{i,c_i}

每个字符恰好仅可以由一个键打出。

按键始终有一个当前选中的字符,记其下标为 kik_i。初始状态下,所有按键的 kik_i 都为 11。

输入当前选中的字符时,只需普通按键,耗时 pp。

如果要输入同一按键上的第 jj 个字符,则需要长按,耗时为

q+∣j−ki∣q + |j - k_i|

注意,这里并不保证 q>pq > p。

此外,还可以使用一种全局切换操作。每次切换都会让所有按键的当前字符同时向后移动一位:

ki←ki mod ci+1.k_i \leftarrow k_i \bmod c_i + 1.

执行一次切换需要耗时 tt。切换可以进行任意次,也可以完全不使用。

现在给定一串需要按顺序输入的字符。请合理安排输入方式以及全局切换的时机,使输入整个序列的总耗时最小。

输入格式

第一行包含五个正整数 n,m,p,q,tn, m, p, q, t,分别表示按键数量、字符总数、普通输入当前字符的耗时、长按的基础耗时以及全局切换一次的耗时。

接下来有 nn 行描述各个按键。

第 ii 行包含一个整数 cic_i,随后给出 cic_i 个整数

wi,1,wi,2,…,wi,ci,w_{i,1}, w_{i,2}, \ldots, w_{i,c_i},

表示该按键能够输入的全部字符。

所有字符恰好对应一个按键。

随后一行包含一个整数 LL,表示待输入序列的长度。

最后一行给出 LL 个整数

s1,s2,…,sL,s_1, s_2, \ldots, s_L,

表示需要按顺序输入的字符。

输出格式

输出一个整数,表示完成整个字符序列所需的最小总耗时。

样例 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≤50001 \le n, m \le 5000,1≤ci≤51 \le c_i \le 5,1≤wi,j,si≤m1 \le w_{i,j}, s_i \le m,1≤L≤1051 \le L \le 10^5,1≤p,q,t≤2×1041 \le p, q, t \le 2 \times 10^4。

保证 1∼m1 \sim m 在 ww 的输入中均出现且只出现一次。

测试点 n≤n \le 特殊性质
1∼41 \sim 4 55 无
5∼75 \sim 7 100100
8∼98 \sim 9 50005000 ci=1c_i = 1
1010 L=1L = 1
11∼1411 \sim 14 所有的 cic_i 都相等
1515 所有 sis_i 都相等
16∼2016 \sim 20 无