Farmer John's NN cows, conveniently numbered 1…N1…N, are standing in a line (1≤N≤5⋅1041≤N≤5⋅104). The iith cow has a breed identifier bibi in the range 1…K1…K, with 1≤K≤501≤K≤50. The cows need your help to figure out how to best transmit a message from cow 11 to cow NN.It takes |i−j**||i−j| time to transmit a message from cow ii to cow jj. However, not all breeds are willing to communicate with each other, as described by a K×KK×K matrix SS, where Sij**=1Sij=1 if a cow of breed ii is willing to transmit a message to a cow of breed jj, and 00 otherwise. It is not necessarily true that Sij=SjiSij=Sji, and it may even be the case that Sii=0Sii=0 if cows of breed ii are unwilling to communicate with each-other.

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

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains NN and KK.The next line contains NN space-separated integers b1**,b2**,…,bNb1,b2,…,bN.

The next KK lines describe the matrix SS. Each consists of a string of KK bits, SijSij being the jjth bit of the iith string from the top.

OUTPUT FORMAT (print output to the terminal / stdout):

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

SAMPLE INPUT:

5 4
1 4 2 3 4
1010
0001
0110
0100

SAMPLE OUTPUT:

6

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

SCORING:

• Test cases 1-5 satisfy N≤1000N≤1000.
• Test cases 6-13 satisfy no additional constraints.