Canadian Computing Competition: 2015 Stage 1, Senior #4

You are travelling on a ship in an archipelago. The ship has a convex hull which is $K$ centimetres thick. The archipelago has $N$ islands, numbered from $1$ to $N$. There are $M$ sea routes amongst them, where the $i^{th}$ route runs directly between two different islands $a_i$ and $b_i$; $(1\le a_i,b_i\le N)$, takes $t_i$ minutes to travel along in either direction, and has rocks that wear down the ship's hull by $h_i$ centimetres. There may be multiple routes running between a pair of islands.

You would like to travel from island $A$ to a different island $B$ $(1\le A,B\le N)$ along a sequence of sea routes, such that your ship's hull remains intact – in other words, such that the sum of the routes' $h_i$ values is strictly less than $K$.

Additionally, you are in a hurry, so you would like to minimize the amount of time necessary to reach island $B$ from island $A$. It may not be possible to reach island $B$ from island $A$, however, either due to insufficient sea routes or the having the ship's hull wear out.

Input Specification

The first line of input contains three integers $K$, $N$ and $M$ $(1\le K\le 200,2\le N\le 2000,1\le M\le 10000)$, each separated by one space.

The next $M$ lines each contain $4$ integers $a_i$, $b_i$, $t_i$ and $h_i$ $(1\le a_i,b_i\le N,1\le t_i\le {10}^5,0\le h_i\le 200)$, each separated by one space. The $i^{th}$ line in this set of $M$ lines describes the $i^{th}$ sea route (which runs from island $a_i$ to island $b_i$, takes $t_i$ minutes and wears down the ship's hull by $h_i$ centimetres). Notice that $a_i\ne b_i$ (that is, the ends of a sea route are distinct islands).

The last line of input contains two integers $A$ and $B$ $(1\le A,B\le N;A\ne B)$, the islands between which we want to travel.

For 20% of marks for this question, $K=1$ and $N\le 200$. For another 20% of the marks for this problem, $K=1$ and $N\le 2000$.

Output Specification

Output a single integer: the integer representing the minimal time required to travel from $A$ to $B$ without wearing out the ship's hull, or -1 to indicate that there is no way to travel from $A$ to $B$ without wearing out the ship's hull.

Sample Input 1

10 4 7
1 2 4 4
1 3 7 2
3 1 8 1
3 2 2 2
4 2 1 6
3 4 1 1
1 4 6 12
1 4

Output for Sample Input 1

7

Explanation of Output for Sample Input 1

The path of length $1$ from $1$ to $4$ would wear out the hull of the ship. The three paths of length $2$ ($[1,2,4]$ and $[1,3,4]$ two different ways) take at least $5$ minutes but wear down the hull too much. The path $[1,2,3,4]$ takes $7$ minutes and only wears down the hull by $7$ centimetres, whereas the path $[1,3,2,4]$ takes $10$ minutes and wears down the hull by $10$ centimetres.

Sample Input 2

3 3 3
1 2 5 1
3 2 8 2
1 3 1 3
1 3

Output for Sample Input 2

-1

Explanation of Output for Sample Input 2

The direct path $[1,3]$ wears down the hull to $0$, as does the path $[1,2,3]$.