题目描述

编号为 $1\ldots N$ 的 $N$ 座城市由单向道路连接。每条道路都有两个相关参数：道路长度和通过这条道路需要支付的通行费（用硬币数表示）。

Bob 和 Alice 过去都住在城市 $1$。Bob 发现 Alice 在他们喜欢玩的纸牌游戏中作弊后，便与她分手，并决定搬到遥远的城市 $N$。他想尽快到达那里，但手头缺钱。

我们要帮助 Bob 找出一条从城市 $1$ 到城市 $N$ 的最短路径，并且这条路径的费用不能超过他拥有的钱数。

输入格式

第一行包含整数 $K$，$0\le K\le 10000$，表示 Bob 在途中最多可以花费的硬币数。

第二行包含整数 $N$，$2\le N\le 100$，表示城市总数。

第三行包含整数 $R$，$1\le R\le 10000$，表示道路总数。

接下来的 $R$ 行中，每行用空格分隔的四个整数 $S,D,L,T$ 描述一条道路：

• $S$ 是起点城市，$1\le S\le N$；
• $D$ 是终点城市，$1\le D\le N$；
• $L$ 是道路长度，$1\le L\le 100$；
• $T$ 是通行费（用硬币数表示），$0\le T\le 100$。

请注意，不同的道路可能具有相同的起点城市和终点城市。

输出格式

输出文件的第一行也是唯一一行，应包含从城市 $1$ 到城市 $N$、总通行费不超过 $K$ 枚硬币的最短路径总长度。

如果这样的路径不存在，只输出数字 -1。

输入样例 #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

输出样例 #1

11

输入样例 #2

0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0

输出样例 #2

-1

输入样例 #3

1
2
1
1 2 2 1

输出样例 #3

2

数据范围

第一行包含整数 $K$，$0\le K\le 10000$，表示 Bob 在途中最多可以花费的硬币数。

第二行包含整数 $N$，$2\le N\le 100$，表示城市总数。

第三行包含整数 $R$，$1\le R\le 10000$，表示道路总数。

• $S$ 是起点城市，$1\le S\le N$；

• $D$ 是终点城市，$1\le D\le N$；

• $L$ 是道路长度，$1\le L\le 100$；

• $T$ 是通行费（用硬币数表示），$0\le T\le 100$。

输出文件的第一行也是唯一一行，应包含从城市 $1$ 到城市 $N$、总通行费不超过 $K$ 枚硬币的最短路径总长度。