import sys
input = sys.stdin.readline

N = int(input())
C = int(input())
V = int(input())
adj_list = [[] for _ in range(N)]
S = list(map(int, input().split()))
T = list(map(int, input().split()))
Y = list(map(int, input().split()))
M = list(map(int, input().split()))

for Si, Ti, Yi, Mi in zip(S, T, Y, M):
    adj_list[Si-1].append((Ti-1, Mi, Yi))
    
dp = [[10**18 for _ in range(C+1)] for _ in range(N)]
dp[0][0] = 0

for i in range(N):
    for j in range(C+1):
        for next_node, w, m in adj_list[i]:
            if j + m <= C:
                dp[next_node][j+m] = min(dp[next_node][j+m], dp[i][j] + w)

ans = 10 ** 18

for i in range(C+1):
    ans = min(ans, dp[N-1][i])

if ans == 10 ** 18:
    print(-1)
else:
    print(ans)