Cheap Traveling

Ivan has to pay out of his own pocket for the trip to the town where the next programming contest is held, and he has only $S$ euro. So he looked up the public transport timetables and the fares in advance.

Call Ivan's home village $1$, the village where the contest takes place $N$, and the other villages he may pass through $2, 3, \dots, N-1$. Ivan found $M$ bus lines. Each line connects village $v$ and village $w$, takes $t$ hours in either direction, and costs $e$ euro per ride. Several buses may connect the same two villages, and those buses may differ in travel time and in fare.

Write a program that finds a route from village $1$ to village $N$ whose fares add up to at most $S$ euro. If several such routes exist, the program must find one where the total time spent sitting in buses is smallest.

Every ride on a line costs that line's fare $e$ and takes that line's time $t$. A route may pass through the same village or the same line more than once, and each pass adds the fare and the time again.

If $N$ is $1$, the start is already the destination, so the total time is $0$.

The first line contains the positive integers $S$, $N$ and $M$, with $S \le 2000$, $N \le 3000$ and $M \le 5000$.

Each of the next $M$ lines contains four integers $v$, $w$, $t$ and $e$ describing one bus line, with $1 \le v \le N$, $1 \le w \le N$, $1 \le t \le 100$ and $1 \le e \le 100$.

Print the total travel time of the route found, on a single line. If no route costs at most $S$ euro, print -1.