import java.util.*

fun main(args: Array<String>){
    val cityCount = readLine()!!.toInt()
    val maxMoney = readLine()!!.toInt()
    val roadCount = readLine()!!.toInt()

    val roadStartList = readLine()!!.split(" ").map { it.toInt() }
    val roadToList = readLine()!!.split(" ").map { it.toInt() }
    val roadChargeList = readLine()!!.split(" ").map { it.toInt() }
    val roadTimeList = readLine()!!.split(" ").map { it.toInt() }

    // start, to, Road
    val road = mutableMapOf<Int, MutableMap<Int, MutableList<Road>>>()

    for(i in roadStartList.indices) {
        val startCity = roadStartList[i]
        val toCity = roadToList[i]
        val charge = roadChargeList[i]
        val time = roadTimeList[i]
        if(!road.containsKey(startCity)) {
            road[startCity] = mutableMapOf()
        }
        if(!road[startCity]!!.containsKey(toCity)) {
            road[startCity]!![toCity] = mutableListOf()
        }
        road[startCity]!![toCity]!!.add(Road(charge, time))
    }

    val queue = LinkedList<Task>()

    // city, charge, time
    val map = mutableMapOf<Int, MutableMap<Int, Int>>()

    queue.push(Task(1, 0, 0))
    while (queue.isNotEmpty()) {
        val task = queue.pop()
        if(!map.containsKey(task.location)) {
            map[task.location] = mutableMapOf()
        }
        if(!map[task.location]!!.containsKey(task.subTotalCharge)) {
            map[task.location]!![task.subTotalCharge] = task.time
        } else if(map[task.location]!![task.subTotalCharge]!! > task.time) {
            map[task.location]!![task.subTotalCharge] = task.time
        } else {
            continue
        }
        road[task.location]?.let {
            it.forEach {
                val toCity = it.key
                it.value.forEach{
                    val subCharge = task.subTotalCharge + it.charge
                    val subTotalTime = task.time + it.time
                    if(subCharge <= maxMoney) {
                        queue.push(Task(toCity, subCharge, subTotalTime))
                    }
                }
            }
        }
    }
    map[cityCount]?.let {
        println(it.minBy { it.value }!!.value)
    } ?: run {
        println("-1")
    }
}

class Road(val charge:Int, val time:Int)
class Task(val location:Int, val subTotalCharge:Int, val time:Int)