9265 - 环境治理

莫比斯国有n个城市，从0～n-1开始编号，这n个城市两两之间有且仅有一条双向道路连接，所有城市之间均可以到达，由于莫比斯国在大力发展工业，进行道路建设，导致道路环境污染严重，且每一条道路的污染程度不一样，每一条道路的污染度为d。当从A城市去往B城市时，存在一条或多条路径可以到达，莫比斯国的人民很看重出行健康，他们会选择一条污染度最小的路线，他们用一个指标P来衡量出行的污染度，P的定义为：
其中d(i,j)表示城市i到j之间的污染度最小路线对应的污染度。
为了改善莫比斯国人民的出行环境，莫比斯国要求所有城市都行动起来，当某个城市进行道路改善时，会将与这个城市直接相连的所有道路污染度减1，每一条道路的污染度下限值为L，当污染度达到道路下限值L时无论再怎么改善，道路的污染度也不会再减少。

城市道路改善计划如下：
第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之间直接相连的那条道路的污染值下限。

输出一行整数，表示答案。