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 2\,000, 1 \le M \le 10\,000)\) , 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 2\,000\) .

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]\) .