KCM 여행

시간 제한3초메모리 제한256 MB

요약

비용과 시간이 정해진 항공편으로 1번 공항에서 N번 공항까지 예산 M 안에서 이동하는 가장 짧은 시간을 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 최단 경로, 그래프
정답자: 아직 제출이 없습니다

문제

찬민이는 Google Code Jam World Finals에 초대받았지만, 구글이 여행비를 최대 $M$ 원까지만 지원한다. 공항 $1$ (인천)에서 공항 $N$ (LA)까지 총 비용이 $M$ 이하인 경로 중 소요시간이 최소인 것을 구하라. 도착할 수 없으면 Poor KCM을 출력한다.

입력

첫 줄: 테스트 케이스 수 $T$ (항상 1)
각 테스트: $N$ , $M$ , $K$ , 이어서 $K$ 개의 항공편 $u$ , $v$ , $c$ , $d$ ( $1 \leq u, v \leq N$ , $u \neq v$ )

출력

각 테스트마다 최소 소요시간 한 줄. 불가능하면 Poor KCM.

예제3

예제 1
입력
```
1
3 100 3
1 2 1 1
2 3 1 1
1 3 3 30
```
예상 출력
```
2
```

예제 2

입력

예상 출력

Poor KCM

예제 3
입력
```
1
2 5 1
1 2 3 7
```
예상 출력
```
7
```