题目描述

给定一个带正权的有向图，它满足以下两个条件：

• 每个顶点至多属于一个简单环；
• 对任意两个顶点 $u,v$，从 $u$ 到 $v$ 至多存在一条简单路径。

图由一个 $n\times n$ 的数字字符矩阵描述。第 $i$ 行第 $j$ 个字符为 0，表示不存在从 $i$ 到 $j$ 的边；否则该字符是 1 到 9，表示从 $i$ 到 $j$ 的有向边的权值。

给定起点 $s$、终点 $t$ 和正整数 $k$，求从 $s$ 到 $t$ 的第 $k$ 短游走的长度。游走可以重复经过顶点和边，因此可以反复绕行图中的环。

如果多条不同游走的长度相同，它们仍要分别计数。如果从 $s$ 到 $t$ 的游走不足 $k$ 条，输出 $-1$。

输入格式

第一行包含四个整数 $n,k,s,t$，分别表示顶点数、所求排名、起点和终点。

接下来 $n$ 行，每行包含一个长度为 $n$ 的数字字符串，描述图的邻接矩阵。

顶点编号为 $0$ 到 $n-1$。

输出格式

输出一个整数，表示从 $s$ 到 $t$ 的第 $k$ 短游走的长度；如果这样的游走不存在，输出 $-1$。

样例 1

4 1 0 2
0100
0020
0003
4000

3

样例 2

4 2 0 2
0100
0020
0003
4000

13

样例 3

3 1 1 2
011
000
000

-1

样例 4

6 3 0 3
010000
001010
000101
000000
010000
001000

5

数据范围与保证

• $2\le n\le50$；
• $1\le k\le10^{12}$；
• $0\le s,t<n$ 且 $s\ne t$；
• 邻接矩阵中的字符均为 0 到 9；
• 矩阵主对角线上的字符均为 0；
• 图满足题目描述中的两项结构限制。

术语说明

• 简单路径是一个顶点互不相同的有序序列，序列中每个顶点都有一条边指向下一个顶点；
• 简单环首尾顶点相同，除首尾外的其余顶点互不相同，并且序列中每个顶点都有一条边指向下一个顶点。

说明

样例 1 中的最短游走为 $0\to1\to2$，长度为 $3$。

样例 2 中可以沿环 $0\to1\to2\to3\to0$ 绕行一次，再到达顶点 $2$，得到长度为 $13$ 的第二短游走。

样例 4 中最短游走长度为 $3$，随后两条不同游走的长度都为 $5$，因此第三短游走的长度为 $5$。