Telephone
Farmer John's n cows, conveniently numbered 1..n, are standing in a line. The i-th cow has a breed identifier b[i] 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 S[ij] = 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 S[ij] = S[ji], and it may even be the case that S[ii] = 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 * 10^4) and k (1 ≤ k ≤ 50).
The next line contains n integers b[1], b[2], ..., b[n].
The next k lines describe the matrix S. Each consists of a string of k bits, S[ij] 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.