아득히 먼 곳

시간 제한2초메모리 제한512 MB

요약

비용 행렬과 예산 m이 주어질 때, 1번 정점에서 시작하며 총 비용이 m 이하인 경로의 간 개수 최댓값을 구합니다. 정점과 간은 여러 번 사용할 수 있습니다.

난이도: 어려움10점 중 8점
유형: 이분 탐색, 그래프, 행렬, 수학
정답자: 아직 제출이 없습니다

문제

여행의 목적은 목적지에 도착하는 것이 아니라 여행 자체를 하는 것이다. 가능한 한 많은 구간을 지나는 여행을 하고 싶다. 하지만 각 구간을 지날 때마다 비용이 들고, 예산은 한정되어 있다. 가장 긴 경로를 찾아라!

입력

첫째 줄에 장소의 수 $n$ ( $1 \le n \le 100$ )과 사용할 수 있는 금액 $m$ ( $1 \le m \le 10^9$ )이 주어진다.

다음 $n$ 개의 줄은 구간을 나타낸다. 각 줄에는 $n$ 개의 정수가 있으며, $i$ 번째 줄의 $j$ 번째 정수 $c_{ij}$ 는 장소 $i$ 에서 장소 $j$ 로 가는 구간의 비용이다 ( $1 \le i, j \le n$ 인 모든 $i, j$ 에 대해 $1 \le c_{ij} \le 10^9$ ). 여행은 장소 1에서 시작해야 하며, 어떤 장소에서든 끝낼 수 있다.

출력

장소 1에서 시작하는 여행 중 구간 비용의 합이 $m$ 이하인 여행이 가질 수 있는 최대 구간 수를 출력한다. 여행은 같은 장소를 여러 번 방문할 수 있고(시작점과 도착점 포함), 같은 구간을 여러 번 지날 수 있다(비용은 지날 때마다 지불한다).

예제4

예제 1
입력
```
2 7
3 2
1 3
```
예상 출력
```
4
```
예제 2
입력
```
3 9
2 5 4
1 2 1
1 1 2
```
예상 출력
```
6
```
예제 3
입력
```
2 1
2 2
1 1
```
예상 출력
```
0
```
예제 4
입력
```
2 3
1 10
10 10
```
예상 출력
```
3
```