#include #include typedef std::pair P; const int inf = 1000000000; int n, c, v; int s[1505], t[1505], y[1505], m[1505]; P cost[55][55]; int dp[55][305]; //iの町にコストjで行くときの最小の時間 int main(){ std::cin >> n >> c >> v; for (int i = 0; i < v; i++)std::cin >> s[i]; for (int i = 0; i < v; i++)std::cin >> t[i]; for (int i = 0; i < v; i++)std::cin >> y[i]; for (int i = 0; i < v; i++)std::cin >> m[i]; for (int i = 0; i < v; i++)cost[s[i] - 1][t[i] - 1] = P(y[i], m[i]); for (int i = 0; i < 55; i++){ for (int j = 0; j < 305; j++){ dp[i][j] = inf; } } dp[0][0] = 0; for (int i = 0; i < n; i++){ for (int j = 0; j <= c; j++){ if (dp[i][j] == inf)continue; for (int k = 0; k < n; k++){ if (cost[i][k].first != 0 && cost[i][k].second != 0 && j + cost[i][k].first <= c)dp[k][j + cost[i][k].first] = std::min(dp[k][j + cost[i][k].first], dp[i][j] + cost[i][k].second); } } } int ans = *std::min_element(dp[n - 1], dp[n - 1] + c + 1); if (ans == inf)ans = -1; std::cout << ans << std::endl; return 0; }