环境治理 ### 问题描述 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_{i j}\left(D_{i j}=D_{j i}, D_{i i}=0\right)$ 表示城市 $i$ 与城市 $j$ 之间直接相连 的那条道路的灰尘度。 接下来 $n$ 行, 每行包含 $n$ 个整数, 相邻两个整数之间用一个空格分隔, 其 中第 $i$ 行第 $j$ 列的值 $L_{i j}\left(L_{i j}=L_{j i}, L_{i i}=0\right)$ 表示城市 $i$ 与城市 $j$ 之间直接相连的 那条道路的灰尘度的下限值。 ### 输出格式 输出一行包含一个整数表示答条。 ### 样例输入 ```text 3 10 0 2 4 2 0 1 4 1 0 0 2 2 2 0 0 2 0 0 ``` ### 样例输出 ```text 2 ``` ### 评测用例规模与约定 对于 $30 \\%$ 的评测用例, $1 \leq n \leq 10 ， 0 \leq L_{i j} \leq D_{i j} \leq 10$ ； 对于 $60 \\%$ 的评测用例, $1 \leq n \leq 50 ， 0 \leq L_{i j} \leq D_{i j} \leq 100000$; 对于所有评测用例, $1 \leq n \leq 100,0 \leq L_{i j} \leq D_{i j} \leq 100000,0 \leq Q \leq 2^{31}-1$ 。