#include using namespace std; /////////////////////////////////////////////////// /// Variables /// /////////////////////////////////////////////////// #define ll long long #define REP(x,n) for(int x=0;x void showendl(T &x){cout< void show(pair &x){cout<<"("< void showendl(pair &x){cout<<"("< void debug(H&& h){showendl(h);} template void debug(H&& h, Ts&&... ts){show(h);debug(forward(ts)...);} template void debug(vector &vt){int i=0;int size = vt.size();for(auto x: vt)++i!=size ? show(x) : showendl(x);} template void debug(vector> &vt){int i=0;int size = vt.size();for(int k=0; k void debug(deque &vt){int i=0;int size = vt.size();for(auto x: vt)++i!=size ? show(x) : showendl(x);} template void debug(stack s){int i=0;int size = s.size();while(!s.empty()){T w = s.top();++i!=size ? show(w) : showendl(w);s.pop();}} template void debug(queue s){int i=0;int size = s.size();while(!s.empty()){T w = s.front();++i!=size ? show(w) : showendl(w);s.pop();}} template void debug(priority_queue s){int i=0;int size = s.size();while(!s.empty()){T w = s.top();++i!=size ? show(w) : showendl(w);s.pop();}} } /////////////////////////////////////////////////// /// Function / Library /// /////////////////////////////////////////////////// // a^b // O(logb) ll intpow(ll a,ll b){ ll ans = 1; while(b){if(b & 1) {ans *= a;} a *= a; b /= 2;}return ans;} // a^b mod p // O(logb) ll modpow(ll a, ll b, ll p){ll ans = 1; while(b){if(b & 1) {(ans *= a) %= p;} (a *= a) %= p; b /= 2;}return ans;} // 負の数にも対応した % 演算 ll mod(ll val, ll m) {ll res = val % m; if (res < 0) res += m; return res;} // mod. m での a の逆元 a^{-1} を計算する 逆元の存在条件: gcd(a, m) = 1 ll modinv(ll a, ll m) {ll b = m, u = 1, v = 0; while (b) {ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v);} u %= m; if (u < 0) u += m; return u;} template inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;} template inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;} // 整数を桁ごとにvectorへ // O(桁数) template vector num_digit (T a){string ss = to_string(a);int size = ss.size();vector v(size);for(int i=0; i ll int digit_length(T a){string ss = to_string(a);return (ll int)ss.size();} // gcd(最大公約数) // O(log(min(a,b))) ll int gcd(ll int a, ll int b){if (a%b == 0){return(b);}else{return(gcd(b, a%b));}} // lcm(最小公倍数)// O(log(min(a,b))) ll int lcm(ll int a, ll int b){return a / gcd(a, b) * b;} ///////////////////////////////////////////////////////////// int main (){ // ifstream in("input.txt"); // cin.rdbuf(in.rdbuf()); int N, C, V; cin >> N >> C >> V; vector S(V), T(V), Y(V), M(V); REP(i,V) {cin >> S[i]; S[i]--;} REP(i,V) {cin >> T[i]; T[i]--;} REP(i,V) cin >> Y[i]; REP(i,V) cin >> M[i]; vector>> G(N); REP(i,V){ G[S[i]].push_back({T[i], i}); } vector> dp(N, vector(C+1, INF)); dp[0][0] = 0; REP(i,N){ for(auto p: G[i]){ int v = p.first; int ind = p.second; REP(j,C+1){ if(j+Y[ind] <= C) chmin(dp[v][j+Y[ind]], dp[i][j] + M[ind]); } } } // debug(dp); int ans = INF; REP(j,C+1){ ans = min(ans, dp[N-1][j]); } if(ans==INF) cout << -1 << endl; else cout << ans << endl; }