\(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\) не передає повідомлення корові своєї породи.

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

Формат вхідних даних

Перший рядок містить \(N\) та \(K\).

Наступний рядок містить \(N\) розділених пробілом цілих чисел \(b_1,b_2,\ldots,b_N\).

Наступні \(K\) рядків описують матрицю \(S\). Кожен рядок складається з рядка K біт. \(S_{ij}\) \(j\)-ий біт \(i\)-ого рядка зверху.

Формат вихідних даних

Виведіть одне ціле число – мінімальна кількість потрібного часу. Якщо неможливо надіслати повідомлення від корови \(1\) до корови \(N\), виведіть \(-1\).

Приклад вхідних даних

5 4
1 4 2 3 4
1010
0001
0110
0100

Приклад вихідних даних

6

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

ОЦІНЮВАННЯ:

• У тестах 1-5 \(N\le 1000\).
• У тестах 6-13 немає додаткових обмежень