在一条直线上，通信管理部门布设了 N 个信号节点构成的通讯链路，按位置从左向后依次编号为 1 \sim N。

每个信号节点有一个具体的设备型号，设第 i 个节点的型号为 T_i (1 \le T_i \le K)。

为了完成一次重要的应急信息广播，工作人员需要将信息 从节点 1 传递到节点 N。

信息可以在满足如下条件的两个节点之间直接传输：

1. 两个节点之间的设备型号必须满足兼容关系表。
2. 如果可以直接传输，则通信时间等于它们的位置差值的绝对值：|i - j|。

设备型号的兼容关系由一个 K \times K 的矩阵 C 给出：

• 若设备型号为 x 的节点可以直接向设备型号为 y 的节点发送信息，则 C_{xy}=1。
• 否则 C_{xy}=0。

注意：

• 不保证 C_{xy} = C_{yx}。
• 某些型号的设备甚至 不允许向相同型号发送信息（可能出现 C_{xx}=0）。

请你编程计算出将信息从节点 1 传递到节点 N 所需的最短时间。如果无法实现传递，输出 -1。

第一行包含两个整数 N, K。

第二行包含 N 个整数 T_1, T_2, \dots, T_N。

接下来 K 行描述兼容性矩阵 C，每行是一个长度为 K 的仅包含 0 和 1 的二进制字符串，从上到下第 x 行的第 y 个字符为 C_{xy}。

输出一个整数，为最短通信时间。若无法传输，输出 -1。

样例 1 说明

一种最优的传输方案为：节点编号序列 1 → 4 → 3 → 5。

最短通信时间计算为：|1-4| + |4-3| + |3-5| = 3 + 1 + 2 = 6。

数据范围

对于 100\% 的数据，满足 1 \le N \le 5 \times 10^4，1 \le K \le 50，1 \le T_i \le K。

月赛分层图图论25年12月