描述

有$N$个城市，编号为$1$到$N$，这些城市通过单向道路连接。每条道路有两个参数：道路长度和通行该道路需要支付的过路费（以硬币数量表示）。

$Bob$和$Alice$原本住在城市$1$。由于$Alice$在他们喜欢的卡牌游戏中作弊，$Bob$决定与她分手并搬离——前往城市$N$。他希望尽快到达那里，但他手头现金有限。

我们需要帮助$Bob$找到从城市$1$到城市$N$的最短路径，且该路径的总过路费不超过他拥有的金额。

输入

第一行包含一个整数$K$（$0 \leq K \leq 10000$），表示$Bob$在路上最多可以花费的硬币数量。

第二行包含一个整数$N$（$2 \leq N \leq 100$），表示城市的总数。

第三行包含一个整数$R$（$1 \leq R \leq 10000$），表示道路的总数。

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

$S$是起点城市（$1 \leq S \leq N$），$D$是终点城市（$1 \leq D \leq N$），

$L$是道路长度（$1 \leq L \leq 100$），$T$是过路费（$0 \leq T \leq 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  

来源

CEOI 1998