n = read_line.to_i
c = read_line.to_i
v = read_line.to_i

s = Array.new(v, 0)
t = Array.new(v, 0)
y = Array.new(v, 0)
m = Array.new(v, 0)

# Read the next 4 lines for S, T, Y, M
s_line = read_line.split.map(&.to_i)
t_line = read_line.split.map(&.to_i)
y_line = read_line.split.map(&.to_i)
m_line = read_line.split.map(&.to_i)

v.times do |i|
  s[i] = s_line[i] - 1
  t[i] = t_line[i] - 1
  y[i] = y_line[i]
  m[i] = m_line[i]
end

graph = Array.new(n) { [] of Tuple(Int32, Int32, Int32) }

v.times do |i|
  graph[s[i]] << {t[i], y[i], m[i]}
end

INF = 1_000_000_000
dp = Array.new(n) { Array.new(c + 1, INF) }
dp[0][c] = 0

n.times do |i|
  c.downto(0) do |k|
    next if dp[i][k] == INF
    graph[i].each do |to, cost, time|
      if k >= cost
        new_k = k - cost
        new_time = dp[i][k] + time
        if new_time < dp[to][new_k]
          dp[to][new_k] = new_time
        end
      end
    end
  end
end

result = dp[n - 1].min
puts result == INF ? -1 : result