Caption

Advanced Caption Machines (ACM) makes electronic captions used as labels, signs, and tags in brick-and-mortar stores, ranging from small shelf tags to large row signs. Every such display shows one line of text on an m × n grid of pixels; each pixel can be individually turned on or off and holds its state indefinitely. If an off pixel is drawn as '.' and an on pixel as '*', then one way to show "ACM ICPC" on a 5 × 53 grid is:

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

Energy is spent only to flip a pixel's state, so the energy needed to change one text into another is proportional to the number of pixels that flip.

When the text changes there is freedom in the layout. The text uses a fixed-width font in which every letter is an m × k grid of pixels. The spacing between two consecutive letters may be anything from smin to smax pixels, and the whole text may also be shifted left or right. This freedom is used to minimize the number of flipped pixels.

For example, changing the caption above to "NEERC" while keeping the spacing between letters between 1 and 2 pixels can be done by flipping only 61 pixels (34 turned off and 27 turned on):

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

Given the text currently displayed together with its exact layout, the new text to display, and the spacing limits, find the minimum number of pixels that must be flipped to display the new text.

The first line contains five integers m, n, k, smin, and smax.

• m (5 ≤ m ≤ 30): the number of rows on the caption
• n (5 ≤ n ≤ 2000): the number of columns on the caption
• k (5 ≤ k ≤ 30): the pixel width of each letter in the font
• smin, smax (0 ≤ smin ≤ smax ≤ 30): the minimum and maximum spacing allowed between letters

The next m lines describe the font. Each of these lines has t(k + 3) − 1 characters, where t (1 ≤ t ≤ 26) is the number of defined letters. These m lines hold t glyphs; each glyph is an m × k grid of '.' and '*' for one uppercase Latin letter (A–Z). On the first of these lines the letter that a glyph represents is printed immediately before that glyph. The first line uses 2t − 1 spaces as separators and each remaining line uses 3t − 1 spaces, laid out exactly as in the example tests. Letters may appear in any order and each letter is defined at most once. The space character is implicitly defined as an m × k grid of '.', and it obeys the same smin/smax spacing limits as any other letter.

The next line is the text currently displayed: ccur characters (1 ≤ ccur ≤ 30) — uppercase Latin letters and spaces, with no leading or trailing spaces.

The next line contains ccur non-negative integers giving the spacing before each character of the current text. The first number is the gap from the left edge of the caption to the first character, the second is the gap between the first and second characters, and so on. The current text fits on the caption, but its spacing need not obey the smin/smax limits.

The next line is the new text to display: cnew characters (1 ≤ cnew ≤ 30) — uppercase Latin letters and spaces, with no leading or trailing spaces.

Every letter used in the current and new text is defined in the font.

Print a single integer: the minimum number of pixels that must be flipped to change the caption from the current text to the new text.

A valid layout places the cnew characters from left to right so that the gap before the first character (measured from the left edge) is non-negative, every gap between two consecutive characters is between smin and smax pixels inclusive, and the whole text fits within the n columns. At least one valid layout always exists.