问题描述

$LQ$ 国拥有 $n$ 个城市, 从 $0$ 到 $n-1$ 编号, 这 $n$ 个城市两两之间都有且仅有一条双向道路连接, 这意味着任意两个城市之间都是可达的。每条道路都有一个属性 $D$, 表示这条道路的灰尘度。当从一个城市 $A$ 前往另一个城市 $B$ 时, 可能存在多条路线, 每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘度之和, $LQ$ 国的人都很讨厌灰尘, 所以他们总会优先选择灰尘度最小的路线。

$LQ$ 国很看重居民的出行环境, 他们用一个指标 $P$ 来衡量 $LQ$ 国的出行环境, $P$ 定义为:

$P=\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} d(i, j)$

其中 $d(i, j)$ 表示城市 $i$ 到城市 $j$ 之间灰尘度最小的路线对应的灰尘度的值。 为了改善出行环境, 每个城市都要有所作为, 当某个城市进行道路改善时, 会将与这个城市直接相连的所有道路的灰尘度都减少 $1$ , 但每条道路都有一个灰尘度的下限值 $L$, 当灰尘度达到道路的下限值时, 无论再怎么改善, 道路的灰尘度也不会再减小了。

具体的计划是这样的:

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

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

$\cdots$

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

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

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

$LQ$ 国想要使得 $P$ 指标满足 $P \leq Q$。请问最少要经过多少天之后, $P$ 指标可以满足 $P \leq Q$。如果在初始时就已经满足条件, 则输出 0 ; 如果永远不可能满足, 则输出 -1。

输入格式

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

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

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

输出格式

输出一行包含一个整数表示答条。

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

2

样例说明

初始时的图如下所示，每条边上的数字表示这条道路的灰尘度：

此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

d(0, 0) = 0,d(0, 1) = 2,d(0, 2) = 3,

d(1, 0) = 2,d(1, 1) = 0,d(1, 2) = 1,

d(2, 0) = 3,d(2, 1) = 1,d(2, 2) = 0.

初始时的 P 指标为 (2 + 3 + 1) × 2 = 12，不满足 P ≤ Q = 10;

第一天，0 号城市进行道路改善，改善后的图示如下：

注意到边 (0, 2) 的值减小了 1 ，但 (0, 1) 并没有减小，因为 L0,1 = 2 ，所以(0, 1) 的值不可以再减小了。此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

d(0, 0) = 0,d(0, 1) = 2,d(0, 2) = 3,

d(1, 0) = 2,d(1, 1) = 0,d(1, 2) = 1,

d(2, 0) = 3,d(2, 1) = 1,d(2, 2) = 0.

此时 P 仍为 12 。

第二天，1 号城市进行道路改善，改善后的图示如下：

此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

d(0, 0) = 0,d(0, 1) = 2,d(0, 2) = 2,

d(1, 0) = 2,d(1, 1) = 0,d(1, 2) = 0,

d(2, 0) = 2,d(2, 1) = 0,d(2, 2) = 0.

此时的 P 指标为 (2 + 2) × 2 = 8 < Q ，此时已经满足条件。

所以答案是 2。

评测用例规模与约定

对于 30% 的评测用例, $1≤n≤10，0≤L_{ij}≤D_{ij}≤10$；

对于 60% 的评测用例, $1≤n≤50，0≤L_{ij}≤D_{ij}≤100000$;

对于所有评测用例, $1≤n≤100，0≤L_{ij}≤D_{ij}≤100000，0≤Q≤2^{31}-1$。