N = int(input())
C = int(input())
V = int(input())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
Y = list(map(int,input().split()))
M = list(map(int,input().split()))
G = [[] for _ in range(N+1)]
for i in range(V):
    G[S[i]].append((T[i],Y[i],M[i]))
inf = 1 << 30
dp = [[inf] * (C + 1) for _ in range(N+1)]
dp[1][0] = 0
for i in range(1,N+1):
    for c in range(C+1):
        for t,y,cc in G[i]:
            if c + y <= C:
                if dp[t][c+y] > dp[i][c] + cc:
                    dp[t][c+y] = dp[i][c] + cc
_min = inf
for c in range(C+1):
    if dp[-1][c] < _min:
        _min = dp[-1][c]
if _min == inf:
    _min = -1
print(_min)