Convex Hull

문제

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 ith route runs directly between two different islands a_i and b_i (1 ≤ a_i, b_i ≤ 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 ≤ A, B ≤ 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’ hi 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.

입력

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

The next M lines each contain 4 integers a_i b_i t_i and h_i (1 ≤ a_i, b_i ≤ N, 1 ≤ t_i ≤ 10⁵, 0 ≤ h_i ≤ 200), each separated by one space. The ith line in this set of M lines describes the ith 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 ≠ 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 ≤ A, B ≤ N; A ≠ B), the islands between which we want to travel.

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

출력

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.

힌트

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 8 minutes. 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 13 minutes and wears down the hull by 5 centimetres.

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

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

7

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

-1