N = int(input())
C = int(input())
V = int(input())
*S, = map(int, input().split())
*T, = map(int, input().split())
*Y, = map(int, input().split())
*M, = map(int, input().split())

G = [[] for _ in [0]*(N+1)]
for s, *t in zip(S, T, Y, M):
    G[s].append(t)

INF = 10**10
D = [[INF]*(C+1) for _ in [0]*(N+1)]
D[1][C] = 0
used = set((1, C))

while True:
    dmin = INF
    z = -1

    for v in range(1, N+1):
        for c in range(C+1):
            if (v, c) not in used and D[v][c] < dmin:
                dmin = D[v][c]
                z = v, c
    if z == -1:
        break

    used.add(z)
    v, c = z
    for u, y, m in G[v]:
        if c-y < 0:
            continue
        if D[v][c]+m < D[u][c-y]:
            D[u][c-y] = D[v][c]+m

ans = min(D[N])
if ans == INF:
    print(-1)
else:
    print(ans)