n, c, v = gets.as(String).split.map(&.to_i)
s = Array.new(v) { gets.as(String).split.map(&.to_i)[0] - 1 }
t = Array.new(v) { gets.as(String).split.map(&.to_i)[0] - 1 }
y = Array.new(v) { gets.as(String).split.map(&.to_i)[0] }
m = Array.new(v) { gets.as(String).split.map(&.to_i)[0] }

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

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

INF = 10**9
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|
      next if k < cost
      dp[to][k - cost] = Math.min(dp[to][k - cost], dp[i][k] + time)
    end
  end
end

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