n коров Фермера Джона, последовательно пронумерованные, 1..n выстроены в ряд. i-ая корова имеет идентификатор породы bi в интервале 1..k. Коровы нуждаются в Вашей помощи чтобы узнать, как быстрее передать сообщение от коровы 1 корове n.

|i − j| минут требуется, чтобы передать сообщение от коровы i к корове j. Однако не все породы готовы взаимодействовать друг с другом, что описано в матрице S размером k * k, где Sij = 1 если корова породы i готова передать сообщение корове породы j и 0 в противном случае. Необязательно истина то, что Sij = Sji, и даже может быть случай, когда Sii = 0, то есть корова породы i не будет передавать сообщение корове своей породы.

Определите минимальное количество времени, которое потребуется для передачи сообщения.

Входные данные

Первая строка содержит n (1 ≤ n ≤ 5 * 104) и k (1 ≤ k ≤ 50).

Следующая строка содержит n целых чисел b1, b2,..., bn.

Следующие k строк описывают матрицу S. Каждая строка состоит из строки из k бит. Sij - это j-ый бит i-ой строки сверху.

Выходные данные

Выведите одно целое число - минимальное количество требуемого времени. Если невозможно передать сообщение от коровы 1 к корове n, выведите −1.

Пример

Оптимальная последовательность передач 1 → 4 → 3 → 5. Общее количество времени есть |1 − 4| + |4 − 3| + |3 − 5| = 6.