새 키보드

Petya는 새 키보드를 샀다. 이 키보드는 n개의 레이아웃을 지원하며, 각 레이아웃에서는 영문 소문자 알파벳의 일부 문자를 입력할 수 있다. 레이아웃에는 1부터 n까지 번호가 붙어 있다.

Petya는 지금 어떤 메시지를 입력하려고 하는데, 이 메시지는 영문 소문자 m개로 이루어져 있다. 처음에는 1번 레이아웃이 활성화되어 있다. Petya는 다음 두 가지 동작 중 하나를 할 수 있다.

• 레이아웃을 다음 것으로 전환한다. 현재 레이아웃이 i라면 새 레이아웃의 번호는 i mod n + 1이며, 여기서 mod는 나눗셈의 나머지를 뜻한다. 직전 동작도 레이아웃 전환이었다면 이 동작에 b밀리초가 걸리고, 그렇지 않다면 a밀리초가 걸린다.
• 문자를 입력한다. 입력한 문자를 현재 메시지의 끝에 덧붙일 수 있다. 이 동작에 c밀리초가 걸린다.

Petya가 메시지를 입력하는 데 필요한 최소 시간을 구하거나, 새 키보드로 그 메시지를 입력하는 것이 불가능한지 판별하라. 마지막에 어떤 레이아웃이 활성화되어 있는지는 중요하지 않다.

첫째 줄에는 네 정수 n, a, b, c가 주어진다. 각각 레이아웃의 수, 직전에 전환하지 않은 상태에서 레이아웃을 전환하는 데 걸리는 밀리초, 직전에 전환한 뒤에 레이아웃을 전환하는 데 걸리는 밀리초, 문자 하나를 입력하는 데 걸리는 밀리초이다 (1 ≤ n ≤ 2 000, 1 ≤ b ≤ a ≤ 10^9, 1 ≤ c ≤ 10^9).

다음 n개 줄에는 레이아웃이 주어진다. 각 레이아웃은 그 레이아웃으로 입력할 수 있는 영문 소문자 알파벳 문자를 모두 담은 문자열로 표현된다. 각 문자는 레이아웃마다 최대 한 번만 등장한다. 각 문자열에서 문자는 알파벳 순으로 정렬되어 있다.

마지막 줄에는 Petya가 입력하려는 메시지 s가 주어진다 (s의 길이는 1 이상 2 000 이하). 문자열 s는 영문 소문자로 이루어져 있다.

메시지를 입력하는 데 필요한 최소 밀리초 수를 정수 하나로 출력한다. 메시지를 입력하는 것이 불가능하면 -1을 출력한다.