#P2165. 大楼

大楼

题目描述

xz 是一个旅游爱好者,这次他来到了一座新的城市。城市中央有一幢高耸入云的大楼。这幢楼到底有多少层呢?据说和非负整数的个数是一样多的。

xz 想爬上这座大楼来观赏新城市的全景。这幢大楼的楼层从下至上用从小到大的非负整数编号。

每层楼有 nn 个房间,用 11 到 nn 的正整数编号。楼层之间用电梯连接,电梯只能上行,不能下行或者同层移动。(下楼一般自行解决)

电梯用 (u,v,w)(u,v,w) 的形式给出,表示对于任意正整数 ii,有第 ii 层的房间 uu 到第 i+wi+w 层的房间 vv 有一部电梯。电梯只能从起点开往终点,不能中途停留。

xz 想要观赏城市全景,至少需要登上第 mm 层楼,即最终需要到达的楼层数 ≥m\ge m。由于乘坐电梯要缴纳高额的费用,而如果花销太大回家就没法报账了,xz 希望乘坐电梯的次数最少。现在 xz 在第 00 层的 11 号房间,你需要求出这个最少的乘坐次数。

输入格式

第一行包含一个正整数 TT,表示数据的组数。

接下来的数据分为 TT 个部分。

每个部分第一行包含两个正整数 nn 和 mm,意义见题目描述。

接下来 nn 行,每行包含 nn 个非负整数。这 nn 行中,第 ii 行第 jj 个数为 wi,jw_{i,j},如果 wi,jw_{i,j} 非零,则表示有电梯 (i,j,wi,j)(i,j,w_{i,j})。同一行各个数之间均用一个空格隔开。

输出格式

对于每组数据,输出一行一个正整数,最少的乘坐次数。

样例输入

2
6 147
0 1 0 50 0 0
0 0 1 0 0 0
20 0 0 0 0 0
0 0 0 0 1 50
0 0 0 8 0 0
0 0 0 0 0 3
6 152
0 1 0 50 0 0
0 0 1 0 0 0
20 0 0 0 0 0
0 0 0 0 1 50
0 0 0 8 0 0
0 0 0 0 0 3

样例输出

9
10

样例说明

第一组数据中,使用电梯的顺序为 $1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 4\rightarrow 6\rightarrow 6$。

第二组数据中,使用电梯的顺序为 $1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 4\rightarrow 5\rightarrow 4\rightarrow 6$。

第二组数据最后到达了 153153 层,但是没有更短的路径使得恰好到达 152152 层,因此答案为 1010。

数据规模与约定

有如下几类具有特点的数据:

  1. 有 10%10\% 的数据所有的 n=2n=2;
  2. 有 20%20\% 的数据 m≤3000m\leq 3000;
  3. 有 20%20\% 的数据对于满足 1≤i,j≤n1\leq i,j\leq n 的整数 ii 和 jj,若 wi,j≠0w_{i,j}\neq 0,则有 wi,j≥1015w_{i,j}\ge 10^{15};
  4. 有 30%30\% 的数据所有的 n=40n=40。

以上各类数据均不包含其他类数据。

对于所有数据 T=5T=5,1≤n≤1001\leq n\leq 100,1≤m≤10181\leq m\leq 10^{18};对于满足 1≤i,j≤n1\leq i,j\leq n 的整数 ii 和 jj,有 0≤wi,j≤10180\leq w_{i,j}\leq 10^{18}。数据保证能够到达 mm 层或更高的楼层。