#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(k,a,b) for(int k=(a); k < (b); k++) #define FORE(k,a,b) for(int k=(a); k <= (b); k++) #define REP(k,a) for(int k=0; k < (a); k++) #define ALL(c) (c).begin(), (c).end() #define EXIST(s,e) ((s).find(e)!=(s).end()) #define RANGE(lb, x, ub) ((lb) <= (x) && (x) < (ub)) #define dump(x) cerr << #x << ": " << (x) << endl; typedef long long ll; typedef vector VI; typedef vector VVI; typedef vector VS; typedef pair PII; const int INF = 1000 * 1000 * 1000; const double EPS = 1e-10; int main() { int N, C, V; cin >> N >> C >> V; VI ss(V), ts(V), ys(V), ms(V); REP(i, V) cin >> ss[i]; REP(i, V) cin >> ts[i]; REP(i, V) cin >> ys[i]; REP(i, V) cin >> ms[i]; VVI costs(N, VI(N, INF)), times(N, VI(N, INF)); REP(i, V) { costs[ss[i]-1][ts[i]-1] = ys[i]; times[ss[i]-1][ts[i]-1] = ms[i]; } VVI dp(N, VI(C+1, INF)); dp[0][0] = 0; FOR(i, 1, N) { FOR(j, 0, i) { if(costs[j][i] < INF) { int cost = costs[j][i]; int t = times[j][i]; FORE(c, 0, C) { if(c + cost <= C) { dp[i][c + cost] = min(dp[i][c + cost], dp[j][c] + t); } else { break; } } } } } int res = INF; FORE(c, 0, C) { res = min(res, dp[N-1][c]); } if(res == INF) res = -1; cout << res << endl; return 0; }