Телефон#11202

Телефон

1 секунда

128 мегабайтів

Складна

Фермер Джон має $n$ корів, пронумерованих від $1$ до $n$ , які стоять в одну лінію. $i$ -та корова має ідентифікатор породи $b_{i}$ b_i, що знаходиться в діапазоні від $1$ до $k$ . Коровам потрібна ваша допомога, щоб визначити оптимальний спосіб передачі повідомлення від корови $1$ до корови $n$ .

Для передачі повідомлення від корови $i$ до корови $j$ потрібно $∣ i - j ∣$ |i - j| одиниць часу. Однак не всі породи готові обмінюватися повідомленнями одна з одною. Можливість передачі повідомлення між породами задається матрицею $S$ розміру $k \times k$ k \times k, де $S_{ij} = 1$ S_{ij} = 1, якщо корова породи $i$ готова передати повідомлення корові породи $j$ , і $S_{ij} = 0$ S_{ij} = 0 в іншому випадку. При цьому не обов'язково, що $S_{ij} = S_{j i}$ S_{ij} = S_{ji}, і навіть може виявитися, що $S_{ii} = 0$ S_{ii} = 0, якщо корови породи $i$ не готові обмінюватися повідомленнями одна з одною.

Визначте мінімальну кількість часу, необхідну для передачі повідомлення від корови $1$ до корови $n$ .

Вхідні дані

Перший рядок містить два цілих числа $n (1 \leq n \leq 5 \cdot 1 0^{4})$ n~(1 \le n \le 5 \cdot 10^4) та $k (1 \leq k \leq 50)$ k~(1 \le k \le 50).

Другий рядок містить $n$ цілих чисел $b_{1}, b_{2}, \dots, b_{n}$ b_1, b_2, \ldots, b_n, де $1 \leq b_{i} \leq k$ 1 \le b_i \le k.

Наступні $k$ рядків описують матрицю $S$ . Кожен рядок містить рядок з $k$ бітів, де $S_{ij}$ S_{ij} — це $j$ -й біт $i$ -го рядка.

Вихідні дані

Виведіть одне ціле число — мінімальну кількість часу, необхідну для передачі повідомлення від корови $1$ до корови $n$ . Якщо передати повідомлення від корови $1$ до корови $n$ неможливо, виведіть $- 1$ .

Приклади

Оптимальна послідовність передач має вигляд $1 \to 4 \to 3 \to 5$ 1 \to 4 \to 3 \to 5. Загальний час передачі складає $∣1 - 4∣ + ∣4 - 3∣ + ∣3 - 5∣ = 6$ |1 - 4| + |4 - 3| + |3 - 5| = 6.

Приклад 1