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

# Read all input at once for better performance
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)

# Build graph directly without intermediate arrays
graph = Array.new(n) { [] of Tuple(Int32, Int32, Int32) }

v.times do |i|
  from = s_line[i] - 1
  to = t_line[i] - 1
  cost = y_line[i]
  time = m_line[i]
  graph[from] << {to, cost, time}
end

INF = 1_000_000_000
# Use 1D array for DP with rolling optimization
dp = Array.new(c + 1, INF)
dp[c] = 0

n.times do |i|
  # Create temporary array to avoid overwriting during iteration
  temp = dp.dup
  
  c.downto(0) do |k|
    next if temp[k] == INF
    
    graph[i].each do |to, cost, time|
      next if k < cost
      
      new_k = k - cost
      new_time = temp[k] + time
      if new_time < dp[new_k]
        dp[new_k] = new_time
      end
    end
  end
end

result = dp.min
puts result == INF ? -1 : result