def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    C = int(input[ptr])
    ptr +=1
    V = int(input[ptr])
    ptr +=1
    S = list(map(int, input[ptr:ptr+V]))
    ptr +=V
    T = list(map(int, input[ptr:ptr+V]))
    ptr +=V
    Y = list(map(int, input[ptr:ptr+V]))
    ptr +=V
    M = list(map(int, input[ptr:ptr+V]))
    ptr +=V

    # Build adjacency list
    adj = [[] for _ in range(N+1)]  # cities are 1-based
    for i in range(V):
        s = S[i]
        t = T[i]
        y = Y[i]
        m = M[i]
        adj[s].append( (t, y, m) )

    INF = float('inf')
    dp = [ [INF] * (C+1) for _ in range(N+1) ]
    dp[1][0] = 0  # starting at city 1, cost 0, time 0

    for i in range(1, N+1):
        for cost in range(C+1):
            if dp[i][cost] == INF:
                continue
            # Process each edge from i
            for (t, y, m) in adj[i]:
                new_cost = cost + y
                if new_cost > C:
                    continue
                if dp[t][new_cost] > dp[i][cost] + m:
                    dp[t][new_cost] = dp[i][cost] + m

    # Find the minimal time for city N with cost <= C
    min_time = INF
    for c in range(C+1):
        if dp[N][c] < min_time:
            min_time = dp[N][c]
    print(min_time if min_time != INF else -1)

if __name__ == '__main__':
    main()