eolymp
bolt
Try our new interface for solving problems
Problems

Cheap traveling

Cheap traveling

Time limit 2 seconds
Memory limit 1024 MiB

Ivan the Speedy has to pay using his own personal funds the travel to the place of the next programming contest. Moreover, he has only s euro. For that reason, he carefully investigated the schedules of the public transportations and the prices, of course. Let us denote by 1 Speedy's birthplace, by n - the place where the contest will take place, and by 2, 3, ..., n - 1 - the other villages he could pass through some of them. In Internet, Ivan found m possibilities for traveling in the form: the bus from village v to village w (as well as from w to v) travels t hours and costs e Euro for each of both directions. There may be more than one bus traveling between v to w, and different buses traveling from v do w may travel for different times and at different ticket prices.

Write a program to find a trip from village 1 to village n at a cost, which is less than or equal to s Euro. If there exists more than one such traveling, the program must find a traveling in which Speedy will spend minimal time sitting in the busses.

Input data

The first line contains the positive integers s, n and m (s2000, n3000, m5000). Each of the next m lines contains 4 integers - parameters v, w, t and e of one transportation possibility (1vn, 1wn, 1t100, 1e100).

Output data

The program has to print the duration of the found trip. If there no trip of cost less than or equal to s, the program has to print -1.

Examples

Input example #1
7 4 6
1 2 2 5
1 3 2 2
1 4 7 3
2 3 1 2
2 4 2 3
3 4 5 2
Output example #1
5
Input example #2
4 4 6
1 2 2 5
1 3 2 2
1 4 7 5
2 3 1 2
2 4 2 3
3 4 5 3
Output example #2
-1
Source 2016 VIII International autumn tournament in informatics, Shumen, Junior, Problem C