Problem C
Ebony and Ivory

A passage from Chopin’s Scherzo No. 1.

Piano fingering describes the process of assigning fingers of a hand to keys on the piano when playing a musical passage. Although professional musicians consider piano fingering an art rather than a science, students often search for finger assignments that make them easier to play.

The goal of this problem is to find an assignment that minimizes the ergonomic difficulty of playing a right-hand passage without chords, i.e., where one note is played at a time.

A standard piano keyboard has $52$ white keys and $36$ black keys for a total of $88$ keys, which are numbered $1 \ldots 88$. These keys are interleaved as shown in Figure . Thus, in this numbering, keys $2, 5, 7, 10$, and $12$ are black, as are any keys whose number is any multiple of $12$ away from these keys (e.g., $14, 17, 19, \ldots $).

A passage is a sequence of notes (each of which corresponds to a key). The difficulty of playing a passage is the sum of the difficulties of playing each interval, i.e., pair of adjacent notes in the passage. A passage of length $L$ thus consists of $L-1$ intervals. An interval’s difficulty depends on the following factors:

• The distance between the keys, which is counted in so-called ‘half steps.’ Stepping from key number $i$ to $i+1$, or from $i$ to $i-1$, is moving one half step. If an interval uses the same key twice in a row (zero half-steps), this key must be played with the same finger because the next note may need to be played connected, or legato. The difficulty of playing intervals in which a note is repeated is zero.

• Which finger is used to play the lower key and which is used to play the upper key. The lower key is the one with the smaller number.

• Whether the lower and upper keys are white or black.

Since these latter two difficulties can vary between players, we use ergonomic tables, which are indexed using pairs of fingers assigned to the lower and upper keys of an interval. The fingers of the right hand are numbered from $1$ (thumb) to $5$ (little finger). Since there are $4$ possible color combinations for the lower and upper key (white/white, white/black, black/white, and black/black) there are $4$ ergonomic tables that describe the transition difficulties. Consult the proper table based on the colors of the lower and upper keys in an interval. Playing an ascending interval has the same difficulty as playing the same interval in descending order if the lower and upper keys are assigned to the same fingers. For example, playing the interval $(41, 43)$ with fingers $(1, 3)$ is as difficult as playing interval $(43, 41)$ with fingers $(3, 1)$ – in both cases, finger $1$ is on key $41$, and finger $3$ is on key $43$.

Input

The input consists of a single test case. The first line contains $5$ positive integers $w_ w$, $w_ b$, $b_ w$, $b_ b$ ($0 < w_ w, w_ b, b_ w, b_ b \le 20$), and $L$ ($1 \le L \le 10\, 000$). Four ergonomic tables follow back-to-back, in the order white/white, white/black, black/white, and black/black, with $w_ w$, $w_ b$, $b_ w$, $b_ b$ entries each. Each table entry is listed on a separate line containing $14$ integers in the following format: $f_ l \ f_ u \ h_1 \ h_2 \ h_3 \ \ldots \ h_{12}$. $h_ i$ ($0 \le h_ i \le 10$) is the relative difficulty of playing an interval of $i$ half steps if finger $f_ l$ is used to play the lower key and finger $f_ u$ is used to play the upper key of the interval. $f_ l$ and $f_ u$ ($1 \le f_ l, f_ u \le 5$, $f_ u \ne f_ l$) denote fingers of the right hand.

The last line of the input contains $L$ integers $a_ i$ ($1 \le a_ i \le 88, |a_{i+1} - a_{i}| \le 12$ for all $i$), which represent the sequence of notes that make up the passage. It is guaranteed that a suitable finger assignment exists.

The tables found in Sample Input $1$ are due to Hart, Bosch, and Tsai.

Output

Output a single number, the minimum total difficulty of playing the given right-hand passage with an optimal finger assignment using only entries of the given ergonomic tables. The optimal finger assignment may start and end with any finger.

11 11 11 10 10
1 2 1 1 1 1 1 1 1 2 2 2 2 3
1 3 1 1 1 1 1 1 1 1 1 2 2 3
1 4 2 2 1 1 1 1 1 1 1 1 1 2
1 5 3 3 2 2 1 1 1 1 1 1 1 1
2 3 1 1 1 1 2 2 3 3 3 3 3 3
2 4 2 2 1 1 1 1 2 3 3 3 3 3
2 5 3 3 2 2 1 1 1 1 1 2 2 2
3 1 2 2 3 3 4 4 4 4 4 4 4 4
3 4 1 1 2 2 3 3 3 3 3 3 3 3
3 5 3 3 1 1 1 1 3 3 3 3 3 3
4 5 1 1 1 1 3 3 3 3 3 3 3 3
1 2 1 1 1 1 1 1 1 1 2 2 3 0
1 3 1 1 1 1 1 1 1 1 1 1 2 0
1 4 2 2 2 1 1 1 1 1 1 1 1 0
1 5 3 3 3 2 2 2 1 1 1 1 1 0
2 3 1 1 1 2 2 3 3 3 3 3 3 0
2 4 2 1 1 1 1 2 2 2 3 3 3 0
2 5 3 2 2 2 2 1 1 1 2 2 3 0
3 1 4 4 4 4 4 4 4 4 4 4 4 0
3 4 1 1 1 3 3 3 3 3 3 3 3 0
3 5 3 2 2 2 2 2 3 3 3 3 3 0
4 5 2 2 2 2 3 3 3 3 3 3 3 0
1 2 3 2 2 1 1 2 2 2 3 3 3 0
1 3 3 2 2 1 1 1 2 2 2 2 3 0
1 4 3 3 3 1 1 1 1 1 2 2 2 0
1 5 3 3 3 2 2 2 1 1 1 1 1 0
2 3 1 1 1 2 2 3 3 3 3 3 3 0
2 4 2 1 1 1 1 2 3 3 3 3 3 0
2 5 3 2 2 1 1 1 1 1 1 1 2 0
3 1 2 3 3 4 4 4 4 4 4 4 4 0
3 4 1 1 1 3 3 3 3 3 3 3 3 0
3 5 2 1 1 1 1 1 2 2 3 3 3 0
4 5 1 1 1 2 2 3 3 3 3 3 3 0
1 2 0 2 2 2 2 0 3 3 3 3 0 3
1 3 0 2 2 2 2 0 2 2 2 2 0 2
1 4 0 3 2 2 2 0 2 1 1 1 0 2
1 5 0 3 3 3 3 0 2 1 1 1 0 1
2 3 0 1 1 1 2 0 3 3 3 3 0 3
2 4 0 2 1 1 1 0 2 3 3 3 0 3
2 5 0 3 2 2 1 0 1 1 1 2 0 2
3 4 0 1 1 1 2 0 3 3 3 3 0 3
3 5 0 3 1 1 2 0 3 3 3 3 0 3
4 5 0 2 2 2 3 0 3 3 3 3 0 3
33 34 39 42 38 41 39 42 46 51

10