전자 캡션

ACM(Advanced Caption Machines)은 상점에서 선반용 작은 태그부터 큰 안내판까지 다양한 용도로 쓰이는 전자 캡션을 만든다. 모든 전자 캡션은 한 줄의 텍스트를 m × n 픽셀 격자로 표시하며, 각 픽셀은 개별적으로 켜거나 끌 수 있고 그 상태를 계속 유지한다. 꺼진 픽셀을 '.', 켜진 픽셀을 '*'로 나타내면, 예를 들어 5 × 53 격자에 "ACM ICPC"를 다음과 같이 표시할 수 있다.

.....*....****.*...*.........*....****.****...****.......*.*..*.....**.**.........*...*.....*...*.*..........*...*.*.....*.*.*.........*...*.....****..*..........*****.*.....*...*.........*...*.....*.....*..........*...*..****.*...*.........*....****.*......****...

픽셀의 상태를 바꿀 때만 에너지가 소모되므로, 한 텍스트를 다른 텍스트로 바꾸는 데 드는 에너지는 상태가 바뀌는(뒤집히는) 픽셀 수에 비례한다.

텍스트를 바꿀 때 배치에는 자유가 있다. 텍스트는 고정폭 글꼴을 사용하며, 각 글자는 m × k 픽셀 격자로 표현된다. 이웃한 두 글자 사이의 간격은 smin 픽셀부터 smax 픽셀까지 가능하고, 텍스트 전체를 좌우로 옮길 수도 있다. 이 자유를 이용해 뒤집히는 픽셀 수를 최소로 만든다.

예를 들어 위 캡션을 글자 사이 간격을 1~2 픽셀로 유지하면서 "NEERC"로 바꾸면, 다음처럼 단 61개의 픽셀만 뒤집으면 된다(34개는 끄고 27개는 켠다).

...................*...*..*****..*****.****...****......................**..*..*......*.....*...*.*..........................*.*.*..***....***...****..*..........................*..**..*......*.....*.*...*..........................*...*..*****..*****.*..*...****...

현재 캡션에 표시된 텍스트와 그 정확한 배치, 새로 표시할 텍스트, 그리고 간격 제한이 주어질 때, 새 텍스트를 표시하기 위해 뒤집어야 하는 픽셀 수의 최솟값을 구하라.

첫째 줄에 다섯 정수 m, n, k, smin, smax가 주어진다.

• m (5 ≤ m ≤ 30): 캡션의 행 수
• n (5 ≤ n ≤ 2000): 캡션의 열 수
• k (5 ≤ k ≤ 30): 글꼴에서 각 글자의 가로 픽셀 폭
• smin, smax (0 ≤ smin ≤ smax ≤ 30): 글자 사이에 허용되는 최소·최대 간격

이어지는 m개의 줄은 글꼴을 설명한다. 각 줄은 t(k + 3) − 1개의 문자로 이루어지며, t (1 ≤ t ≤ 26)는 정의된 글자의 개수이다. 이 m개의 줄에는 t개의 글리프가 들어 있고, 각 글리프는 대문자 알파벳(A–Z) 한 글자를 나타내는 '.'과 '*'로 된 m × k 격자이다. 이 중 첫째 줄에는 각 글리프가 나타내는 글자가 해당 글리프 바로 앞에 적혀 있다. 첫째 줄은 구분용으로 모두 2t − 1개의 공백을, 나머지 줄은 각각 3t − 1개의 공백을 사용하며, 배치 형식은 예제 입력과 동일하다. 글자는 어떤 순서로도 나올 수 있으며, 각 글자는 많아야 한 번 정의된다. 공백 문자는 m × k 격자가 모두 '.'인 글자로 암묵적으로 정의되어 있으며, 다른 글자와 마찬가지로 smin·smax 간격 제한을 따른다.

그다음 줄에는 현재 표시된 텍스트가 주어진다. 이 문자열은 ccur개의 문자(1 ≤ ccur ≤ 30)로, 대문자 알파벳과 공백으로 이루어지며 앞뒤에 공백이 없다.

그다음 줄에는 ccur개의 음이 아닌 정수가 주어지며, 현재 텍스트의 각 문자 앞 간격을 나타낸다. 첫 번째 수는 캡션 왼쪽 끝에서 첫 문자까지의 간격, 두 번째 수는 첫 문자에서 두 번째 문자까지의 간격, … 순이다. 현재 텍스트는 캡션 안에 들어가지만, 그 간격이 smin·smax 제한을 따를 필요는 없다.

그다음 줄에는 새로 표시할 텍스트가 주어진다. 이 문자열은 cnew개의 문자(1 ≤ cnew ≤ 30)로, 대문자 알파벳과 공백으로 이루어지며 앞뒤에 공백이 없다.

현재 텍스트와 새 텍스트에 쓰인 모든 글자는 글꼴에 정의되어 있다.

현재 텍스트에서 새 텍스트로 캡션을 바꿀 때 뒤집어야 하는 픽셀 수의 최솟값을 정수 하나로 출력하라.

올바른 배치란 cnew개의 문자를 왼쪽에서 오른쪽으로 놓되, 첫 문자 앞 간격(왼쪽 끝에서 잰 값)은 0 이상이고, 이웃한 두 문자 사이의 모든 간격은 smin 이상 smax 이하이며, 텍스트 전체가 n개의 열 안에 들어가는 배치를 말한다. 올바른 배치는 항상 하나 이상 존재한다.