| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 29 | 18 | 16 | 72.727% |
As you know, the purpose of a journey is not to reach the destination but to make the trip. You want to make a trip with as many legs as possible. However, each leg of the trip costs some money and your budget is limited. Find the longest path!
The first line contains two integers n (1 ≤ n ≤ 100), which is the number of locations, and m (1 ≤ m ≤ 109), which is the amount of available money.
The next n lines describe the legs. Each of these lines contains n integers, where the jth integer of the ith line cij is the cost of a leg from location i to location j (1 ≤ cij ≤ 109 for each 1 ≤ i, j ≤ n). Your trip must start at location 1 and may end at any location.
Display the maximum number of legs a trip from location 1 can have such that the sum of the costs of its legs is at most m. A trip may repeatedly visit the same location (including start and destination) and repeatedly use the same leg (paying its cost multiple times).
2 7 3 2 1 3
4
3 9 2 5 4 1 2 1 1 1 2
6
2 1 2 2 1 1
0
2 3 1 10 10 10
3