# include # include # include # include # include # include # include # include # include # include # include # include # include # include # include #include #include #include #include #include using namespace std; typedef long long int ll; const int N = 1000000; const int INF = 1 << 30; #define rep(i,n) for(int i=(ll)0;i<(ll)n;++i) #define ALL(x) x.begin(),x.end() #define pp pair #define fi first #define se second string YN(bool b) { return(b ? "YES" : "NO"); } string yn(bool b) { return(b ? "Yes" : "No"); } struct edge { ll to; ll c; ll t; }; ll V, E, money,mn=INF; vector edges[50]; void dfs(ll pos, ll ti,ll mo,bitset<52>bit2){ cout << pos << "," << ti << "," << mo << "," << bit2 << endl; if (mo >= money)return; if (ti >= mn)return; if (pos == V - 1) { if (mo <= money)mn = min(mn, ti); return; } bitset<52>bit=bit2; bit[pos] = 1; rep(i, (ll)edges[pos].size())if (!bit[edges[pos][i].to]) { dfs(edges[pos][i].to,edges[pos][i].t+ti,edges[pos][i].c+mo,bit); } } int main(){ ll from[1500], to[1500], cost[1500], tm[1500]; cin >> V >> money >> E; rep(i, E)cin >> from[i],from[i]--; rep(i, E)cin >> to[i],to[i]--; rep(i, E)cin >> cost[i]; rep(i, E)cin >> tm[i]; rep(i, E) { //if(from[i]==0||from[i]==20||from[i]==26||from[i]==27)cout << from[i] << "," << to[i] << "," << cost[i] << "," << tm[i] << endl; edges[from[i]].push_back(edge{to[i], cost[i],tm[i]}); } bitset<52>abe; dfs(0, 0, 0, abe); cout << (mn == INF ? -1:mn) << endl; return 0; }