题目描述

FJ 的农场有 n 个小镇, 奶牛 Bessi 在小镇 0 ,它的学校在小镇 n-1。Bessi 要坐车到学校去上学。N 个小镇之间有公交车, Bessi 就是坐公交车去上学。

小镇之间有 m 部公交车,我们用 (a, b, leave, time, cost) 来描述一部公交车的信息: 表示有一部公交车在时刻 leave 从小镇 a 出发, 经过 time 分钟到达城市 b , 车票价格是 cost 。

由于 Bessi 今天睡过头了,他希望在 t 分钟以内(包括 t 分钟)从小镇 0 到达小镇 n-1 。他应该怎样坐公交车才能用最少的车费又能准时上学? 注意: 若bessi在时刻x刚好到达小镇a, 如果公交车的出发时刻也恰好是时刻x, 那么我们规定 Bessi 无法坐到该公交车,也就是说如果想坐这趟公交车则必须在时刻 x 之前到达小镇 a 。当然,有一种情况例外, 小镇 0 的公交车如果是 0 时刻出发, Bessi在时刻 0 是可以坐这趟公交车的。 0 时刻 Bessi 在小镇 0 处。

输入格式

第 1 行: 三个整数 n, t, m，其中 2 ≤ n ≤ 50 , 1 ≤ m ≤ 50 , 1 ≤ t ≤ $10^4$ ；

第 2 至 m+1 行: 每行五个整数: a, b, leave, time, cost, 描述一部公交车的信息，其中 0 ≤ a ≤ n-1 ; 0 ≤ b ≤ n-1 ; 0 ≤ leave ≤ $10^4$ ; 1 ≤ time ≤ $10^4$; 1 ≤ cost ≤ $10^6$ 。

输出格式

Bessi 至少需要多少车费才能在 t 分钟内从小镇 0 到达小镇 n-1 ? 如果无法准时到达,输出 -1 。

样例

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

7

3 7 4
0 1 0 5 1
1 2 6 1 40
0 1 1 2 5
1 2 4 2 5

10