配点 : 800 点
問題文
高桥君是一个字符串 对于 a ,以下内容 可以执行 2 类型的操作。 在
- a 的开头或结尾 1 删除字符。这包括 它的成本是 X 会产生成本。
- a 末尾, 1 添加字符。这包括 Y 会产生成本。
高桥君现在是N 字符串 S_0,S_1,\cdots,S_{N-1} 。 高桥君的朋友青木君告诉高桥君以下的事情。 问 Q 问题。
- 質問 i (0 \leq i \leq Q-1): 青木君是一个字符串 显示 T_i 。 对 T_i 重复上述操作,看看高桥有什么。 找出匹配任何 N 字符串所需的最低成本。
高桥君,请在百忙之中编写一个程序来回答这些问题。
制約
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq X,Y \leq 10^9
- 1 \leq |S_i|
- \sum_{i=0}^{N-1} |S_i| \leq 5 \times 10^5
- S_i \neq S_j (i \neq j)
- 1 \leq |T_i|
- \sum_{i=0}^{Q-1} |T_i| \leq 5 \times 10^5
- T_i \neq T_j (i \neq j)
- 输入的所有数字均为整数。
- 所有输入字符串均由小写英文字母组成。
入力
输入是按以下格式从标准输入给出的。
N Q X Y
S_0
S_1
\vdots
S_{N-1}
T_0
T_1
\vdots
T_{Q-1}
出力
Q 行。 i+1 (0 \leq i \leq Q-1) 行包含问题 i 的答案。 对于第
入力例 1
3 3 4 2 b bcd cd a ab abc
出力例 1
6 4 6
例如,问题 考虑到 2 ,最好的操作方法如下。 删除
abc的第一个字符并 获取bc。成本是 4 需要。bc结束时 输出为d和bcd。成本是 2 需要。
入力例 2
4 3 1 100 a aaaa aaaaaaa aaaaaaaaaa aaa aaaaaa aaaaaaaaa
出力例 2
2 2 2
入力例 3
10 10 86 69 bbabbaaaaa babaababab bbababbbba aaaaaaaaab bbbbbbaabb aabbabbbba babbbbbbaa baaabbaaaa aaaaababbb ababaaaaaa bbaabbbbaa abbbbabbbb abbaaabaaa ababaaaaab bbaabbaaaa abbbbbbabb aabbbabbba aaabbbaaaa abbbababab babaaabbbb
出力例 3
930 620 775 155 775 465 775 930 620 620