Optimal Message Transmission

Farmer John has (N) cows numbered from (1) to (N) standing in a line ((1 \le N \le 5\cdot10^4)). The (i)-th cow belongs to breed (b_i) ((1 \le b_i \le K)) where (1 \le K \le 50). Farmer John wishes to transmit an important message from cow (1) to cow (N).

The time to transmit a message from cow (i) to cow (j) is (|i-j|). However, not all breeds are willing to communicate with each other. This is specified by a (K \times K) matrix (S) where (S_{ij} = 1) if a cow of breed (i) is willing to transmit a message to a cow of breed (j) and (S_{ij} = 0) otherwise. Note that (S) is not necessarily symmetric and it is possible that (S_{ii} = 0) (i.e. cows of the same breed might not talk to each other).

Your task is to determine the minimum total time needed to transmit the message from cow (1) to cow (N).

inputFormat

The input begins with a line containing two integers (N) and (K).

The next line contains (N) integers: (b_1, b_2, \dots, b_N), where (b_i) is the breed number of the (i)-th cow.

This is followed by (K) lines, each containing (K) integers. The (j)-th number in the (i)-th line is (S_{ij}).

outputFormat

Output a single integer: the minimum time required to transmit the message from cow (1) to cow (N). If it is impossible to do so under the given restrictions, output a value representing impossibility (for this problem, you can assume that a solution always exists).

sample

5 3
1 2 3 2 3
0 1 1
0 1 1
0 0 1

4