#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define yn(joken) cout<<((joken) ? "Yes" : "No")<<endl
#define YN(joken) cout<<((joken) ? "YES" : "NO")<<endl
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vd = vector<double>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
const int INF = 1e9;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (int i = 0; i < int(v.size()); i++) {
        is >> v[i];
    }
    return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0; i < int(v.size()); i++) {
        os << v[i];
        if (i < int(v.size()) - 1) os << ' ';
    }
    return os;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N,C,V;
    cin>>N>>C>>V;
    vector<vector<tuple<int,int,int>>> G(N);
    vi S(V),T(V),Y(V),M(V);
    cin>>S>>T>>Y>>M;
    rep(i,V){
        G[S[i]-1].emplace_back(T[i]-1,Y[i],M[i]);
    }
    vvi DP(N,vi(C+1,INF));
    DP[0][0]=0;
    rep(i,N-1){
        for(auto [to,cost,time]:G[i]){
            rep(j,C+1){
                if(DP[i][j]==INF) continue;
                if(j+cost>C) continue;
                chmin(DP[to][j+cost],DP[i][j]+time);
            }
        }
    }
    int ans=INF;
    rep(i,C+1) chmin(ans,DP[N-1][i]);
    cout<<(ans==INF ? -1 : ans)<<endl;
}