Musical Instrument Transitions

An unknown musical instrument has \(S\) holes. Each note is produced by covering the holes in one of 10 ways (digits 0 through 9). However, only \(N\) specific coverings (notes) are allowed. In other words, you are only allowed to play these \(N\) notes.

You are given a musical piece of length \(L\) (notes are given by their index from 1 to \(N\) corresponding to the \(N\) allowed coverings). Due to physical constraints, the instrument does not allow two consecutive notes to differ in the covering pattern by more than \(G\) holes; formally, if you view the covering of a note as a string of length \(S\), then for any two consecutive notes the Hamming distance between their coverings must be \(\le G\). Because the intended piece might not satisfy this constraint, you may have to intentionally play a note different from the intended one. Your goal is to choose a valid sequence of notes (each chosen from the allowed set) that minimizes the number of notes in which your played note differs from the intended note.

The Hamming distance between two coverings is the number of positions (holes) where the digits differ. For example, the Hamming distance between 0123 and 1123 is 1.

Input/Output Formats are described below.

inputFormat

The first line contains four integers \(S\), \(N\), \(G\), and \(L\) representing the number of holes, the number of allowed notes, the maximum allowed difference between coverings of consecutive notes, and the length of the musical piece, respectively.

The next \(N\) lines each contain a string of length \(S\) consisting of digits (0-9), representing an allowed covering (note).

The last line contains \(L\) integers (each between 1 and \(N\), inclusive) representing the intended sequence of notes (by index).

outputFormat

Output a single integer: the minimal number of notes you have to play incorrectly (i.e. the minimal number of positions for which the played note does not match the intended note) so that adjacent played notes have a Hamming distance \(\le G\).

sample

3 3 1 4
000
001
101
1 2 3 2

0