Телефон
n корів Фермера Джона, пронумеровані від 1 до n, стоять у ряд. Кожна корова i має ідентифікатор породи b[i], який знаходиться в діапазоні від 1 до k. Корови потребують вашої допомоги, щоб якомога швидше передати повідомлення від корови 1 до корови n.
Передача повідомлення від корови i до корови j займає |i − j| хвилин. Проте не всі породи готові взаємодіяти одна з одною. Це описано в матриці S розміром k на k, де S[ij] дорівнює 1, якщо корова породи i може передати повідомлення корові породи j, і 0 в іншому випадку. Зверніть увагу, що S[ij] не обов'язково дорівнює S[ji], і може бути так, що S[ii] = 0, тобто корова породи i не може передати повідомлення іншій корові тієї ж породи.
Визначте мінімальний час, необхідний для передачі повідомлення.
Вхідні дані
Перший рядок містить n (1 ≤ n ≤ 5 * 10^4) і k (1 ≤ k ≤ 50).
Другий рядок містить n цілих чисел b[1], b[2], ..., b[n].
Наступні k рядків описують матрицю S. Кожен рядок складається з k бітів. S[ij] - це j-ий біт i-го рядка зверху.
Вихідні дані
Виведіть одне ціле число - мінімальний час, необхідний для передачі повідомлення. Якщо неможливо передати повідомлення від корови 1 до корови n, виведіть −1.
Приклад
Оптимальна послідовність передач: 1 → 4 → 3 → 5. Загальний час: |1 − 4| + |4 − 3| + |3 − 5| = 6.