Under construction

Still being built. Things may change

Highway

Time limit2sMemory limit128 MB

Summary
Given a directed graph with edge lengths and tolls, find the minimum length path from city 1 to city N whose total toll does not exceed a budget K.
Level

Medium5 of 10

Topics
Dynamic programming, Graph, Shortest path
Solved
No attempts yet

Problem

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.

Input

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.

Output

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

If no route is possible, print -1.

Examples2

  1. Example 1

    Input
    5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
    Expected output
    11

  2. Example 2

    Input
    0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0
    Expected output
    -1