n=input()
c=input()
input()
l=[dict() for _ in range(n+1)]
l[1][0]=0
for s,t,y,m in sorted(zip(*[map(int,raw_input().split()) for _ in range(4)])):
    for k,v in l[s].iteritems():
        if k+y<=c: l[t][k+y]=min(l[t].get(k+y,1e9),v+m)
print min(l[n].values()) if len(l[n])>0 else -1