#include #include #include #include #include #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--) #define rep(i, n) for (int i = 0; i < (n); i++) #define rep1(i, n) for (int i = 1; i <= (n); i++) #define rrep(i, n) for (int i = (n)-1; i >= 0; i--) #define pb push_back #define mp make_pair #define fst first #define snd second #define show(x) cout << #x << " = " << x << endl #define chmin(x, y) x = min(x, y) #define chmax(x, y) x = max(x, y) #define pii pair #define vi vector using namespace std; template ostream& operator<<(ostream& o, const pair& p) { return o << "(" << p.first << "," << p.second << ")"; } template ostream& operator<<(ostream& o, const vector& vc) { o << "sz = " << vc.size() << endl << "["; for (const T& v : vc) o << v << ","; o << "]"; return o; } typedef long long ll; #define NMAX 51 #define MAX 101 #define CMAX 301 #define inf 1e9 + 7 int N, C, V; int S[MAX]; int T[MAX]; int Y[MAX]; int M[MAX]; int data[NMAX][CMAX]; struct edge { int to; int cost; int tim; }; vector edges[NMAX]; int main() { cin >> N >> C >> V; rep(i, V) { cin >> S[i]; } rep(i, V) { cin >> T[i]; } rep(i, V) { cin >> Y[i]; } rep(i, V) { cin >> M[i]; } rep(i, V) { edges[S[i]].pb(edge{T[i], Y[i], M[i]}); } rep(i, N + 1) { rep(j, C + 1) { data[i][j] = inf; } } rep(i, C + 1) { data[1][i] = 0; } rep1(i, N) { for (const auto& j : edges[i]) { int to = j.to; int cost = j.cost; int tim = j.tim; rep(c, C + 1) { if (c + cost <= C) { chmin(data[to][c + cost], data[i][c] + tim); } } } } if (data[N][C] >= inf) { cout << -1 << endl; } else { cout << data[1][C] << endl; } return 0; }