struct Edge
  property to : Int32
  property cost : Int32
  property time : Int32

  def initialize(@to, @cost, @time)
  end
end

struct State
  property node : Int32
  property used_cost : Int32
  property total_time : Int32

  def initialize(@node, @used_cost, @total_time)
  end

  def >(other : State) : Bool
    @total_time > other.total_time
  end
end

def shortest_path(n : Int32, c : Int32, graph : Array(Array(Edge))) : Int32
  # DP table: min time to reach each node with a cost
  dp = Array.new(n) { Array.new(c + 1, Int32::MAX) }
  pq = [] of State
  
  dp[0][0] = 0
  pq << State.new(0, 0, 0)
  
  while !pq.empty?
    # Use min_by to simulate priority queue behavior
    curr_index = pq.index(&.total_time).not_nil!
    curr = pq.delete_at(curr_index)
    
    next if curr.total_time > dp[curr.node][curr.used_cost]
    
    graph[curr.node].each do |edge|
      new_cost = curr.used_cost + edge.cost
      new_time = curr.total_time + edge.time
      
      if new_cost <= c && new_time < dp[edge.to][new_cost]
        dp[edge.to][new_cost] = new_time
        pq << State.new(edge.to, new_cost, new_time)
      end
    end
  end
  
  ans = dp[n - 1].min
  ans == Int32::MAX ? -1 : ans
end

# Read input
n, c, v = gets.not_nil!.split.map(&.to_i)
graph = Array.new(n) { [] of Edge }

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

gets.not_nil!.split.each_with_index { |val, i| s[i] = val.to_i }
gets.not_nil!.split.each_with_index { |val, i| t[i] = val.to_i }
gets.not_nil!.split.each_with_index { |val, i| y[i] = val.to_i }
gets.not_nil!.split.each_with_index { |val, i| m[i] = val.to_i }

# Build graph
v.times do |i|
  from = s[i] - 1  # Convert to zero-based indexing
  to = t[i] - 1    # Convert to zero-based indexing
  graph[from] << Edge.new(to, y[i], m[i])
end

puts shortest_path(n, c, graph)