N个城市编号为1……N，两个城市之间只有一条路相连。每条路上有两个参数：路的长度与支付在这条路的过路费。
　　Bob 和Alice 原本住在城市1。当他被告知Alice在一种他们常玩的游戏卡中作假时，他决定结束他们朋友的关系，搬到城市N。他想尽快地到达那里，但他所拥有的现金有限。
　　请你编一程序帮助Bob找到一条最短的路从城市1到N，且能用所所有的钱支付路上的费用。

　　输入数据

　　输入文件ROADS.IN 的第一行包含整数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 是is 通过这条路的过路费，0 ≤ T ≤100

　　输出数据

　　输出文件ROADS.OUT 包含仅有的一行，为一条最短路径从城市1到城市N的长度，且这条路径的总过路费小于Bob的钱。
　　如果这样的路不存在，输出文件中输出-1。

　　Examples

　
　　ROADS.IN

　　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

　　ROADS.OUT

　　11
　　
　　ROADS.IN

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

　　ROADS.OUT

　　-1