Telephone#11202
Farmer John's cows, conveniently numbered from to , are standing in a line. The -th cow has a breed identifier b_i in the range from to . The cows need your help to determine the best way to transmit a message from cow to cow .
It takes |i - j| units of time to transmit a message from cow to cow . However, not all breeds are willing to communicate with each other, as described by a k \times k matrix , where S_{ij} = 1 if a cow of breed is willing to transmit a message to a cow of breed , and S_{ij} = 0 otherwise. It is not necessarily the case that S_{ij} = S_{ji}, and it may even be the case that S_{ii}=0 if cows of breed are unwilling to communicate with each other.
Please determine the minimum amount of time needed to transmit the message from cow to cow .
The first line contains two integers n~(1 \le n \le 5 \cdot 10^4) and k~(1 \le k \le 50).
The second line contains integers b_1, b_2, \ldots, b_n, where 1 \le b_i \le k.
The next lines describe the matrix . Each line contains a string of bits, where S_{ij} is the -th bit of the -th string.
Print one integer representing the minimum amount of time needed to transmit the message from cow to cow . If it is impossible to transmit the message from cow to cow , output .
The optimal sequence of transmissions is 1 \to 4 \to 3 \to 5. The total amount of time is |1 - 4| + |4 - 3| + |3 - 5| = 6.
Example 1