题目描述

N个以1...N标号的城市通过单向道路相连，每条道路包含两个参数：道路长度和通行费（金币数）。 Bob原住在城市1，现在要搬到城市N，需要在总通行费不超过金币预算K的前提下，找到从1到N的最短路径长度，若不存在这样的路径则输出-1。

时间限制：1000ms 内存限制：65536KB

输入描述

第一行包含整数K（0 ≤ K ≤ 10000），代表Bob能花费的最大金币数。 第二行包含整数N（2 ≤ N ≤ 100），代表城市数目。 第三行包含整数R（1 ≤ R ≤ 10000），代表道路数目。 接下来R行，每行四个整数S、D、L、T：

• S：道路起始城市（1 ≤ S ≤ N）
• D：道路终点城市（1 ≤ D ≤ N）
• L：道路长度（1 ≤ L ≤ 100）
• T：通行费（0 ≤ T ≤ 100） 注：不同道路可能有相同的起点和终点。

输出描述

输出一行整数，即满足预算约束的从1到N的最短路径长度，不存在则输出-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