import sys
input = sys.stdin.readline
inf = 10 ** 18

def dijkstra2(N):
    ind = 0
    D = [inf] * (N)
    seen = [False] * (N)
    D[0] = 0
    while True:
        minv = inf
        ind = N + 1
        for i in range(N):
            if seen[i]:
                continue
            if D[i] < minv:
                ind = i
                minv = D[i]
        if ind == N + 1:
            break
        if ind // (C + 1) == N - 1:
            return D
        seen[ind] = True
        for u, d in G[ind]:
            if seen[u]:
                continue
            D[u] = min(D[u], D[ind] + d)
    return D

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()))
N2 = N * (C + 1)
G = [[] for i in range(N2)]
for i in range(V):
    s, t = S[i] - 1, T[i] - 1
    for c in range(C + 1):
        if c + Y[i] <= C:
            G[s * (C + 1) + c].append((t * (C + 1) + c + Y[i], M[i]))

D = dijkstra2(N2)
ans = inf
for i in range(C + 1):
    ans = min(ans, D[(N - 1) * (C + 1) + i])

print(ans) if ans != inf else print(-1)