Телефон
Телефон
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.
5 4 1 4 2 3 4 1010 0001 0110 0100
6