module Main;

import BinaryHeap;
import BoolArray;
import CPLib.Arithmetic;
import CPLib.DSegtree;
import CPLib.Graph;
import CPLib.IO;
import CPLib.LDSegtree;
import CPLib.UnionFind;
import CPLib.ZP;
import HashMap;
import HashSet;

main : IO () = (
    let n = *read_i;
    let c = *read_i;
    let v = *read_i;
    let ss = *read_is(v);
    let ss = ss.map(|x| x - 1);
    let ts = *read_is(v);
    let ts = ts.map(|x| x - 1);
    let ys = *read_is(v);
    let ms = *read_is(v);

    let encode = |vertex, money| (
        vertex * (c+1) + money
    );
    let decode = |i| (
        (i / (c+1), i % (c+1))
    );

    let graph = GraphBuilder::create(n*(c+1));
    let graph = range(0, v).fold(graph, |vi, graph|
        let s = ss.@(vi);
        let t = ts.@(vi);
        let y = ys.@(vi);
        let m = ms.@(vi);
        range(0, c+1).fold(graph, |money, graph|
            if money < y { graph };
            let s_money = money;
            let t_money = money - y;
            let s = encode(s, s_money);
            let t = encode(t, t_money);
            graph.add_edge(s, t, m)
        )
    );
    let graph = graph.build;
    let levels = graph.dijkstra(encode(0, c));
    let ans = range(0, c+1).map(|money|
        let i = encode(n-1, money);
        levels.@(i)
    ).fold(I64::maximum, min);
    let ans = if ans == I64::maximum { -1 } else { ans };
    println(ans.to_string)
);