题目描述

小H和他的朋友小W都住在HelloWorld市，HelloWorld市有N个小区，编号为1...N，小H住在小区1，小W住在小区N。有M班公交在这N个小区之间穿梭，每班公交都有一个出发小区S和一个终点小区D，以及从S到D的线路和票价。（途中不会经过其他小区）。有一天小H想要去找小W，但是他只有K元钱，请帮助小H查找从他所在的小区1乘坐公交到达小W所在的小区N，总花费不超过K的前提下，替代最短的公交换乘线路。

输入格式

第1行：3个空格分隔的整数，分别表示小H拥有的金钱数量K（0 <= K <= 10000），HelloWorld市的小区数量N（1 <= N <= 100），以及HelloWorld市的公交班次M（1 <= M <= 10000）。
接下来M行：每行4个空格分隔的整数，表示一班公交的信息，其中第i行的4个整数分别表示第i班公交的起点小区S，终点小区D（1 <= S, D <= N）、行驶路程L(1 <= L <= 100)和所需消耗C(0 <= C <= 100）。（注意：从S到D的公交并不能从D到S，同时两个一个城市之间可能有多个不同交通和价格的公交班次）。

输出格式

1行：一个整数，表示在总花费不超过K的前提下，小H要从小区1到达小区N的最短路程，如果无法到达小区N，则输出-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

output

11