道路

N个以 1 ... N 标号的城市通过单向的道路相连。每条道路包含两个参数：道路的长度和需要为该路付的通行费（以金币的数目来表示）

Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后，Bob和她分手了，并且决定搬到城市N。他希望能够尽可能快的到那，但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的路径，前提是他能够付的起通行费。

输入格式

第一行包含一个整数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所需要的最小的路径长度（花费不能超过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

限制

时间限制：1000ms，内存限制：64MiB