Sanjindra is close to finding the All Blue and fulfilling their dream! However, there remains yet one obstacle in their path: a treacherous portion of the Calm Belt filled with evil sea monsters. Sanjindra knows that their ship, the Thousand Sunny, is strong and can take less than ~k~ points of damage before that it will sink.

The portion of the Calm Belt can be modelled as a graph with ~n~ nodes, connected by ~m~ routes. Each route has a two endpoints (~a_i~ and ~b_i~), a distance (~w_i~), and the damage the sea monsters will do (~d_i~).

As Namindra, the navigator of the ship, it is your job to find the shortest route from nodes ~x~ to ~y~ which takes less than ~k~ points of damage. Can you help Sanjindra with this task?

Input Format

The first line of input will consist of 3 integers, ~k~ ~n~ ~m~. Each of the next lines will consist of 4 integers ~a_i~ ~b_i~ ~w_i~ and ~d_i~, as described in the description. Finally, the last line will contain two integers ~x~ and ~y~, the point Sanjindra starts and wants to end.

Output Format

The output should consist of a single integer, the minimum length of the path if it is possible, or 1 if it is not.

Constraints

~1 \le k \le 200~

~2 \le n \le 2000~

~n \le m \le 10000~

~0 \le a_i, b_i \le n-1~

~1 \le w_i \le 1e5~

~0 \le c_i \le 200~

Sample Input

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

Sample Output

7