N, C, V = (int(input()) for _ in range(3))
tmp = list(zip(*[tuple(map(int, input().split())) for _ in range(4)]))
W = [[] for _ in range(N + 1)]
for t in tmp:
    W[t[0]].append(t[1:])

table = [[float('inf')] * (C + 1) for _ in range(N + 1)]  # 1-indexed
table[1][0] = 0
for s in range(1, N + 1):
    for c in range(C):
        if table[s][c] == float('inf'):
            continue
        for t, y, m in W[s]:
            if c + y > C:
                continue
            table[t][c + y] = min(table[t][c + y], table[s][c] + m)

print(ans if (ans := min(table[N])) != float('inf') else -1)