Farmer John's n cows, conveniently numbered 1..n, are standing in a line. The i-th cow has a breed identifier bi in the range 1...k. The cows need your help to figure out how to best transmit a message from cow 1 to cow n.

It takes |i − j| time to transmit a message from cow i to cow j. However, not all breeds are willing to communicate with each other, as described by a k * k matrix S, where Sij = 1 if a cow of breed i is willing to transmit a message to a cow of breed j, and 0 otherwise. It is not necessarily true that Sij = Sji, and it may even be the case that Sii = 0 if cows of breed i are unwilling to communicate with each-other.

Please determine the minimum amount of time needed to transmit the message.

Input

The first line contains n (1 ≤ n ≤ 5 * 104) and k (1 ≤ k ≤ 50).

The next line contains n integers b1, b2, ..., bn.

The next k lines describe the matrix S. Each consists of a string of k bits, Sij being the j-th bit of the i-th string from the top.

Output

Print a single integer giving the minimum amount of time needed. If it is impossible to transmit the message from cow 1 to cow n, then output −1.

Example

The optimal sequence of transmissions is 1 → 4 → 3 → 5. The total amount of time is |1 − 4| + |4 − 3| + |3 − 5| = 6.