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

Input Specification

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 ai, bi, ti and hi (1≤a$_i$,b$_i$≤N,1≤t$_i$≤10$^5$,0≤h$_i$≤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$≠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 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].