Highway

During spring camp, highway tolls rose sharply. The participants must return home using only the transportation money they prepared before the toll increase, so exceeding the budget may leave them stuck in Sokcho.

Cities are numbered vertices, and each road is a one-way edge from one city to another. Every road has a length and a toll. Sokcho is city 1, and your home is city N.

If it is possible to travel from city 1 to city N without spending more than the prepared budget K, find the minimum possible total length of such a route. If no such route exists, output -1.

The first line contains the prepared transportation budget K. (0 <= K <= 10,000)

The second line contains the number of cities N. (2 <= N <= 100)

The third line contains the number of roads R. (1 <= R <= 10,000)

Each of the next R lines describes one road with four integers s, d, l, and t.

• s: the starting city of the road
• d: the destination city of the road
• l: the length of the road
• t: the toll of the road

The values satisfy 1 <= s <= N, 1 <= d <= N, 1 <= l <= 100, and 0 <= t <= 100.

City numbers from 1 through N are all used. Every road is one-way, and multiple distinct roads may have the same starting city and the same destination city.

Print the length of the shortest route that can be used within the given budget.

If no route is possible, print -1.