KCM Travel

Time limit3sMemory limit256 MB

Summary

Find the fastest route from airport 1 to airport N using flights with costs and times without exceeding budget M, or report that it is impossible.

Level: Medium6 of 10
Topics: Dynamic programming, Shortest path, Graph
Solved: No attempts yet

Problem

Chanmin qualified for Google Code Jam World Finals, but Google pays at most $M$ for travel. Given flights with cost and duration between airports, find the minimum travel time from airport 1 (Incheon) to airport $N$ (LA) with total cost at most $M$ . If impossible, print Poor KCM.

Input

Line 1: integer $T$ (always 1)
Per test: integers $N$ , $M$ , $K$ , then $K$ lines with $u$ , $v$ , $c$ , $d$

Output

For each test, print the minimum time, or Poor KCM if no route fits the budget.

Examples3

Example 1
Input
```
1
3 100 3
1 2 1 1
2 3 1 1
1 3 3 30
```
Expected output
```
2
```

Example 2

Input

Expected output

Poor KCM

Example 3
Input
```
1
2 5 1
1 2 3 7
```
Expected output
```
7
```