from collections import deque
INF = 10 ** 10
def inp() -> str : return input()
def i() -> int : return int(input())
def lis() -> list[int] : return list(map(int, input().split()))

n = i()
c = i()
v = i()
ss = lis()
tt = lis()
ys = lis()
ms = lis()

graph = [[] for _ in range(n)]
for s, t, y, m in zip(ss, tt, ys, ms):
  graph[s - 1].append([t - 1, y, m])

cost = [[INF] * (c + 1) for _ in range(n)]
cost[0][c] = 0

que = deque([(c, 0)])
while que:
  c, s = que.popleft()
  for t, y, m in graph[s]:
    if y <= c and cost[t][c - y] > cost[s][c] + m:
      cost[t][c - y] = cost[s][c] + m
      que.append((c - y, t))
ans = min(cost[n - 1])
print(-1 if ans == INF else ans)