\(N\) con bò của Farmer John, được đánh số \(1\ldots N\), đang đứng thành một hàng (\(1\le N\le 5\cdot10^4\)). Con bò thứ \(i\) có mã giống \(b_i\) trong đoạn \(1\ldots K\), với \(1\le K\le 50\). Đàn bò cần bạn giúp tìm cách tốt nhất để truyền một thông điệp từ bò \(1\) đến bò \(N\).

Truyền thông điệp từ bò \(i\) đến bò \(j\) mất \(|i-j|\) đơn vị thời gian. Tuy nhiên, không phải mọi giống bò đều sẵn sàng liên lạc với nhau. Điều này được mô tả bằng ma trận \(S\) kích thước \(K\times K\), trong đó \(S_{ij}=1\) nếu một con bò giống \(i\) sẵn sàng truyền thông điệp cho một con bò giống \(j\), và bằng \(0\) nếu không. Không nhất thiết \(S_{ij}=S_{ji}\); thậm chí có thể \(S_{ii}=0\) nếu bò giống \(i\) không sẵn sàng liên lạc với nhau.

Hãy xác định thời gian ít nhất cần thiết để truyền thông điệp.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\).

Dòng tiếp theo chứa \(N\) số nguyên \(b_1,b_2,\ldots,b_N\), cách nhau bởi dấu cách.

\(K\) dòng tiếp theo mô tả ma trận \(S\). Mỗi dòng là một xâu gồm \(K\) bit; \(S_{ij}\) là bit thứ \(j\) của xâu thứ \(i\) tính từ trên xuống.

Dữ liệu ra

In một số nguyên là thời gian ít nhất cần thiết. Nếu không thể truyền thông điệp từ bò \(1\) đến bò \(N\), in \(-1\).

Phân nhóm

• Các test 1-5 thỏa mãn \(N\le 1000\).
• Các test 6-13 không có ràng buộc bổ sung.

Ví dụ

5 4
1 4 2 3 4
1010
0001
0110
0100

6

Nguồn

USACO 2021 January Contest, Gold - Telephone: https://usaco.org/index.php?page=viewproblem2&cpid=1090

Tác giả: Dhruv Rohatgi.