|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||2||2||2||100.000%|
Petya has bought a new keyboard. It supports n layouts, each layout allows to input some subset of characters of the lowercase English alphabet. Layouts are enumerated from 1 to n.
Petya wants to type some message now, it consists of m lowercase letters of the English alphabet. Initially the first layout is active. Petya can do one of the following two actions:
Help Petya to find out what minimal time he needs to type the message, or detect that it is impossible to type the message using his new keyboard. The final layout of the keyboard doesn't matter.
The first line of the input data contains four integers n, a, b and c — the number of layouts, the number of milliseconds, to switch the layout without a previous switch, to switch the layout after a switch, and to type a character, respectively (1 ≤ n ≤ 2 000, 1 ≤ b ≤ a ≤ 109, 1 ≤ c ≤ 109).
The following n lines describe the layouts. Each layout is described by a string that contains all lowercase characters of the English alphabet that can be typed using this layout. Each character is specified at most once for each layout. Characters in each string are ordered alphabetically.
The last line contains a string s — the message that the Petya wants to type (length of s is from 1 to 2 000, inclusive). The string s consists of lowercase English letters.
Output one integer — the minimum number of milliseconds needed to type the message. Output - 1 if it is impossible to type the message.
5 3 2 1 abc d e f def abcdef
1 1 1 1 a z