Description

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处.

Format

Input

第1行: 三个整数:n, t, m. 2 <= n <= 50, 1 <= m <= 50. 1 <=t<=10^4.

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

Output

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

Samples

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 4
0 1 1 2 5
1 2 4 2 5 

5

Limitation

1s, 1024KiB for each test case.