#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int MAX_N = 51; int dp[MAX_N][MAX_N]; int pathCost[MAX_N][MAX_N]; int pathTime[MAX_N][MAX_N]; int main(){ int n; cin >> n; int c; cin >> c; int v; cin >> v; int s[v]; int t[v]; int y[v]; int m[v]; int dp[n+1][n+1][c+1]; for(int i = 0; i < 4; i++){ for(int j = 0; j < v; j++){ if(i == 0){ cin >> s[j]; }else if(i == 1){ cin >> t[j]; }else if(i == 2){ cin >> y[j]; }else{ cin >> m[j]; } } } memset(pathCost, -1, sizeof(pathCost)); memset(pathTime, -1, sizeof(pathTime)); memset(dp, -1, sizeof(dp)); dp[0][1][0] = 0; for(int i = 0; i < v; i++){ int from = s[i]; int to = t[i]; int cost = y[i]; int time = m[i]; pathCost[from][to] = cost; pathTime[from][to] = time; } int minTime = INT_MAX; for(int step = 1; step <= n; step++){ bool update = false; for(int from = 1; from <= n; from++){ for(int cost = 0; cost <= c; cost++){ if(dp[step-1][from][cost] >= 0){ for(int to = 1; to <= n; to++){ if(pathCost[from][to] > 0){ int nextCost = cost + pathCost[from][to]; int nextTime = dp[step-1][from][cost] + pathTime[from][to]; if(nextCost <= c){ update = true; if(to == n && minTime > nextTime){ minTime = nextTime; } if(dp[step][to][nextCost] == -1){ dp[step][to][nextCost] = nextTime; }else{ dp[step][to][nextCost] = min(dp[step][to][nextCost], nextTime); } } } } } } } if(!update){ break; } } if(minTime == INT_MAX){ cout << -1 << endl; }else{ cout << minTime << endl; } return 0; }