n=int(input())
c=int(input())
v=int(input())
f=lambda:map(int,input().split())
g=[[]for i in range(n)]
for s,t,y,m in zip(f(),f(),f(),f()):g[t-1].append((s-1,y,m))
dp=[-~c*[1<<20]for i in range(n)]
dp[0][0]=0
for i in range(n):
    for j,k,l in g[i]:
        for m in range(k,c+1):dp[i][m]=min(dp[i][m],dp[j][m-k]+l)
r=min(dp[-1])
print(r if r<1<<20 else -1)