n, c, v = read_line.split.map(&.to_i)
s = read_line.split.map(&.to_i)
t = read_line.split.map(&.to_i)
y = read_line.split.map(&.to_i)
m = read_line.split.map(&.to_i)

# Convert to 0-based indexing
s.map! { |x| x - 1 }
t.map! { |x| x - 1 }

edges = Array.new(n) { [] of Tuple(Int32, Int32, Int32) }
v.times do |i|
  edges[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
    edges[i].each do |to, cost, time|
      next if k < cost
      new_k = k - cost
      new_time = dp[i][k] + time
      dp[to][new_k] = new_time if new_time < dp[to][new_k]
    end
  end
end

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