#include using namespace std; int goforward(int N, int C, int V, int S[], int T[], int Y[], int M[], int start, int curcost, int curtime) { if (start == N) { return curtime; } int smallest = 1e+7; for (int i = 0; i < V; i++) { if (S[i] == start) { int nexcost = curcost + Y[i]; if (nexcost > C) {continue;} int nextime = curtime + M[i]; int result = goforward(N, C, V, S, T, Y, M, T[i], nexcost, nextime); //cout << start << " -> " << T[i] << ": " << result << endl; smallest = min(smallest, result); } } return smallest; } int main(void) { int N, C, V; cin >> N; cin >> C; cin >> V; int S[V], T[V], Y[V], M[V]; for (int i = 0; i < V; i++) { cin >> S[i]; } for (int i = 0; i < V; i++) { cin >> T[i]; } for (int i = 0; i < V; i++) { cin >> Y[i]; } for (int i = 0; i < V; i++) { cin >> M[i]; } int result = goforward(N, C, V, S, T, Y, M, 1, 0, 0); if (result >= 1e+7) {result = -1;} cout << result << endl; return 0; }