题目来源：https://acs.jxnu.edu.cn/problem/NOIOPJCH0403726

重点词汇：

parameters：n.参数

maximum：n.最大，极大

ROADS

道路

描述：

N cities named with numbers 1 ... N are connected with one-way roads. Each road has two parameters associated with it : the road length and the toll that needs to be paid for the road (expressed in the number of coins). N个以数字命名的城市与单向道相连。每一条道路都有两个与它相关的参数：道路的长度和所需要支付的通行费用（用硬币的 数目来表示）
Bob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away - to the city N. He wants to get there as quickly as possible, but he is short on cash. We want to help Bob to find the shortest path from the city 1 to the city N that he can afford with the amount of money he has. 鲍勃和爱丽丝曾经住在城市1。在注意到爱丽丝在他们喜欢玩的纸牌游戏中作弊后，鲍勃打破了和她的关系，决定搬走 - 到 N 市。 他想尽快到达那里，但是他的现金很短缺。 我们想要帮助鲍勃在他所能支付得起的范围内找一条从城市1到城市N最短的路径。

输入：

The first line of the input contains the integer K, 0 <= K <= 10000, maximum number of coins that Bob can spend on his way.
The second line contains the integer N, 2 <= N <= 100, the total number of cities.
The third line contains the integer R, 1 <= R <= 10000, the total number of roads.
Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters : 第一行的输入包含一个整数K，0<=K<=10000，他能在路上花费的最大硬币数量 第二行输入包含一个整数N，2<=N<=100，城市的总数量 第三行输入包含一个整数R，1<=R<=10000，道路的总数量 后面跟着的R行则通过以单个空格分隔的整数S，D，L，T来描述一条路

• S is the source city, 1 <= S <= N
• D is the destination city, 1 <= D <= N
• L is the road length, 1 <= L <= 100
• T is the toll (expressed in the number of coins), 0 <= T <=100

　　S表示起始城市，1<=S<=N 　　D表示目标城市，1<=D<=N 　　L表示路的长度，1<=L<=100 　　T表示费用（用硬币的数量），0<=T<=100
Notice that different roads may have the same source and destination cities. 注意不同的路径可能由相同的起始和目标城市

输出：

The first and the only line of the output should contain the total length of the shortest path from the city 1 to the city N whose total toll is less than or equal K coins.
If such path does not exist, only number -1 should be written to the output.

　　输出的第一行也是唯一一行应该包含从城市 1 到城市 N 的最短路径的总长度，其总通行费小于或等于 K 个硬币。
如果这样的路径不存在，则只应将数字 -1 写入输出。

样例输入：

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

样例输出：

11

注释：

Source: CEOI 1998