该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

雨，有时是会引起人一点淡淡的乡愁的。李商隐的《夜雨寄北》是为许多久客的游子而写的。我有一天在积雨少住的早晨和德熙从联大新校舍到莲花池去。看了池里的满池清水，看了作比丘尼装的陈圆圆的石像（传说陈圆圆随吴三桂到云南后出家，暮年投莲花池而死），雨又下起来了。莲花池边有一条小街，有一个小酒店，我们走进去，要了一碟猪头肉，半市斤酒（装在上了绿釉的土磁杯里），坐了下来，雨下大了。酒店有几只鸡，都把脑袋反插在翅膀下面，一只脚着地，一动也不动地在檐下站着。酒店院子里有一架大木香花，昆明木香花很多。有的小河沿岸都是木香，但是这样大的木香却不多见。一棵木香，爬在架上，把院子遮得严严的。密匝匝的细碎的绿叶，数不清的半开的白花和饱涨的花骨朵，都被雨水淋得湿透了。我们走不了，就这样一直坐到午后。

节选自 ：汪曾祺《昆明的雨》

题目描述

$wqsing$非常开心，因为他终于到昆明旅游了，据说昆明的雨特别好看，所以他打算前往几个景点去看昆明的雨。他希望去的景点有 $n$ 个，编号为 $1,2,3, ... , n$ ，其中从第 $i$ 个景点去往第 $j$ 个景点的车程时间为 $t[i][j]$ ，目前他位于景点 $1$ 。掌管昆明下雨的神为这 $n$ 个地方布置了下雨魔法，这 $n$ 个地方一直下着昆明的雨。现在 $wqsing$ 由于需要回校准备期末考试，所以需要在时间 $m$ 或之前回到景点 $1$ 。请问 $wqsing$ 最多能观赏多少景点的昆明的雨。请注意，$wqsing$ 不需要移动就已经欣赏了景点 $1$ 的雨。

输入格式

前一行两个数 $n, m$ 。

接下来 $n$ 行，每行 $n$ 个数 $,t_{i, j}$ 表示第 $i$ 个景点到第 $j$ 个景点的车程时间。

输出格式

一个整数，表示wqsing最多能观赏多少景点的昆明的雨。

样例 #1

样例输入 #1

3 4
0 2 1
1 0 2
2 1 0

样例输出 #1

3

样例 #2

样例输入 #2

11 2518
0 22 232 1712 1004 1258 279 1613 1663 919 1517 
1512 0 916 1123 105 308 1439 580 570 213 1412 
915 1743 0 0 1890 1883 382 1471 105 130 772 
1160 696 1591 0 585 582 253 816 331 1180 1392 
1903 736 1217 1893 0 502 1893 480 566 1994 344 
1511 363 1432 1783 1843 0 711 934 1864 953 931 
1316 1692 1983 801 898 585 0 1559 1352 1070 1009 
1702 1846 398 1605 1163 201 353 0 808 0 264 
1860 1142 251 1670 109 1325 461 1458 0 628 749 
890 445 1452 531 1835 1687 895 521 1748 0 908 
1023 1188 577 1070 1784 1917 61 1915 351 571 0

样例输出 #2

8

提示

数据范围及约定

对于 $100\%$ 数据 $2 \le n \le 20, 0 \le m \le 2e5, 0 \le t[i][j] \le 10000$。