\(N\) коров Фермера Джона, последовательно пронумерованные, \(1 \ldots N\) выстроены в ряд
(\(1\le N\le 5\cdot 10^4\)). \(i\)-ая корова имеет идентификатор породы \(b_i\)
в интервале \(1 \ldots K\), with \(1\le K\le 50\). Коровы нуждаются в Вашей помощи
чтобы узнать, как быстрее передать сообщение от коровы \(1\) корове \(N\).
\(|i-j|\) минут требуется, чтобы передать сообщение от коровы \(i\) к корове \(j\).
Однако не все породы готовы взаимодействовать друг с другом, что описано
в матрице \(S\) размером \(K \times K\), где \(S_{ij} = 1\) если корова породы \(i\)
готова передать сообщение корове породы \(j\) и 0 в противном случае. Необязательно
истина то, что \(S_{ij}=S_{ji}\), и даже может быть случай, когда \(S_{ii} = 0\),
то есть корова породы \(i\) не будет передавать сообщение корове своей породы.
Определите минимальное количество времени, которое потребуется для передачи
сообщения.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) и
\(K\).
Следующая строка содержит \(N\) разделённых пробелом целых чисел \(b_1,b_2,\ldots,b_N\).
Следующие \(K\) строк описывают матрицу \(S\). Каждая строка состоит из строки из K бит.
\(S_{ij}\) \(j\)-ый бит \(i\)-ой строки сверху.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите одно целое число - минимальное количество требуемого времени.
Если невозможно передать сообщение от коровы \(1\) к корове \(N\), выведите \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
1 4 2 3 4
1010
0001
0110
0100
|
6
|