{"raw_statement":[{"iden":"statement","content":"LQ 国拥有 $n$ 个城市，从 $0$ 到 $n - 1$ 编号，这 $n$ 个城市两两之间都有且仅有一条双向道路连接，这意味着任意两个城市之间都是可达的。每条道路都有一个属性 $D$，表示这条道路的灰尘度。当从一个城市 A 前往另一个城市 B 时，可能存在多条路线，每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘度之和，LQ 国的人都很讨厌灰尘，所以他们总会优先选择灰尘度最小的路线。\n\nLQ 国很看重居民的出行环境，他们用一个指标 $P$ 来衡量 LQ 国的出行环境，$P$ 定义为：\n\n$$P=\\sum \\limits_{i=0}^{n-1} \\sum \\limits_{j=0}^{n-1} d(i,j)$$\n\n其中 $d(i,j)$ 表示城市 $i$ 到城市 $j$ 之间灰尘度最小的路线对应的灰尘度的值。\n\n为了改善出行环境，每个城市都要有所作为，当某个城市进行道路改善时，会将与这个城市直接相连的所有道路的灰尘度都减少 $1$，但每条道路都有一个灰尘度的下限值 $L$，当灰尘度达到道路的下限值时，无论再怎么改善，道路的灰尘度也不会再减小了。\n\n具体的计划是这样的：\n\n- 第 $1$ 天，$0$ 号城市对与其直接相连的道路环境进行改善；\n- 第 $2$ 天，$1$ 号城市对与其直接相连的道路环境进行改善；\n\n……\n- 第 $n$ 天，$n - 1$ 号城市对与其直接相连的道路环境进行改善；\n- 第 $n + 1$ 天，$0$ 号城市对与其直接相连的道路环境进行改善；\n- 第 $n + 2$ 天，$1$ 号城市对与其直接相连的道路环境进行改善；\n\n……\n\nLQ 国想要使得 $P$ 指标满足 $P \\leq Q$。请问最少要经过多少天之后，$P$ 指标可以满足 $P \\leq Q$。如果在初始时就已经满足条件，则输出 $0$；如果永远不可能满足，则输出 $-1$。"},{"iden":"input","content":"输入的第一行包含两个整数 $n, Q$，用一个空格分隔，分别表示城市个数和期望达到的 $P$ 指标。\n\n接下来 $n$ 行，每行包含 $n$ 个整数，相邻两个整数之间用一个空格分隔，其中第 $i$ 行第 $j$ 列的值 $D_{i,j} (D_{i,j}=D_{j,i},D_{i,i} = 0)$ 表示城市 $i$ 与城市 $j$ 之间直接相连的那条道路的灰尘度。\n\n接下来 $n$ 行，每行包含 $n$ 个整数，相邻两个整数之间用一个空格分隔，其中第 $i$ 行第 $j$ 列的值 $L_{i,j} (L_{i,j} = L_{j,i}, L_{i,i} = 0)$ 表示城市 $i$ 与城市 $j$ 之间直接相连的那条道路的灰尘度的下限值。"},{"iden":"output","content":"输出一行包含一个整数表示答案。"},{"iden":"note","content":"**【样例说明】**\n\n初始时的图如下所示，每条边上的数字表示这条道路的灰尘度：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/5lz6auke.png)\n\n此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：\n\n- $d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3$；\n- $d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1$；\n- $d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0$。\n\n初始时的 $P$ 指标为 $(2 + 3 + 1) \\times 2 = 12$，不满足 $P \\leq Q = 10$;\n\n第一天，$0$ 号城市进行道路改善，改善后的图示如下：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/mrhf5wx6.png)\n\n注意到边 $(0, 2)$ 的值减小了 $1$，但 $(0, 1)$ 并没有减小，因为 $L_{0,1} = 2$ ，所以 $(0, 1)$ 的值不可以再减小了。此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：\n\n- $d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3$，\n- $d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1$，\n- $d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0$。\n\n此时 $P$ 仍为 $12$。\n\n第二天，1 号城市进行道路改善，改善后的图示如下：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/tjxis3yb.png)\n\n此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：\n\n- $d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 2$，\n- $d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 0$，\n- $d(2, 0) = 2, d(2, 1) = 0, d(2, 2) = 0$。\n\n此时的 $P$ 指标为 $(2 + 2) \\times 2 = 8 < Q$，此时已经满足条件。\n\n所以答案是 $2$。\n\n**【评测用例规模与约定】**\n\n- 对于 $30\\%$ 的评测用例，$1 \\leq n \\leq 10$，$0 \\leq L_{i,j} \\leq D_{i,j} \\leq 10$；\n- 对于 $60\\%$ 的评测用例，$1 \\leq n \\leq 50$，$0 \\leq L_{i,j} \\leq D_{i,j} \\leq 10^5$；\n- 对于所有评测用例，$1 \\leq n \\leq 100$，$0 \\leq L_{i,j} \\leq D_{i,j} \\leq 10^5$，$0 \\leq Q \\leq 2^{31} - 1$。\n\n蓝桥杯 2022 国赛 A 组 F 题。"}],"translated_statement":null,"sample_group":[["3 10\n0 2 4\n2 0 1\n4 1 0\n0 2 2\n2 0 0\n2 0 0","2\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}