5515: 环境治理(govern)

莫比斯国有 n 个城市，从 0~n-1 开始编号，这 n 个城市两两之间有且仅有一条双向道路连接，所有城市之间均可以到达，由于莫比斯国在大力发展工业，进行道路建设，导致道路环境污染严重，且每一条道路的污染程度不一样，每一条道路的污染度为 d。当从 A 城市去往 B 城市时，存在一条或多条路径可以到达，莫比斯国的人民很看重出行健康，他们会选择一条污染度最小的路线，他们用一个指标 P 来衡量出行的污染度，P 的定义为：

为了改善莫比斯国人民的出行环境，莫比斯国要求所有城市都行动起来，当某个城市进行道路改善时，会将与这个城市直接相连的所有道路污染度减 1，每一条道路的污染度下限值为 ，当污染度达到道路下限值 时无论再怎么改善，道路的污染度也不会再减少。

其中d(i, j)表示城市 i 到 j 之间的污染度最小路线对应的污染度。

为了改善莫比斯国人民的出行环境，莫比斯国要求所有城市都行动起来，当某个城市进行道路改善时，会将与这个城市直接相连的所有道路污染度减 1，每一条道路的污染度下限值为 ，当污染度达到道路下限值 时无论再怎么改善，道路的污染度也不会再减少。

城市道路改善计划如下：

第 1 天，0 号城市对与其直接相连的道路环境进行改善；

第 2 天，1 号城市对与其直接相连的道路环境进行改善；

……

第 n 天，n-1 号城市对与其直接相连的道路环境进行改善；

第 n+1 天，0 号城市对与其直接相连的道路环境进行改善；

第 n+2 天，1 号城市对与其直接相连的道路环境进行改善；

……

莫比斯国想要使得P<=Q。请问最少需要经过多少天之后，P指标可以满足P<=Q。如果还没开始改善就已经满足条件，则输出 0；如果经过改善却始终无法满足条件，则输出 -1。

第一行输入两个整数 $n$、$Q$，两个数之间用空格隔开，分别表示城市个数和期望达到的 $P$ 指标。 

接下来的 $n$ 行，每行包含 $n$ 个整数，相邻两个整数之间用一个空格隔开，其中第 $i$ 行第 $j$ 列的值 $D_{i,j}$ ($D_{i,j} = D_{j,i}, D_{i,i} = 0$) 表示城市 $i$ 与城市 $j$ 之间相连的那条道路的污染度。 

接下来的 $n$ 行，每行包含 $n$ 个整数，相邻两个整数之间用一个空格隔开，其中第 $i$ 行第 $j$ 列的值 $L_{i,j}$ ($L_{i,j} = L_{j,i}, L_{i,i} = 0$) 表示城市 $i$ 与城市 $j$ 之间直接相连的那条道路的污染值下限。 

3 10
0 2 4
2 0 1
4 1 0
0 2 2
2 0 0
2 0 0

2