#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

struct Route
{
	int town1;
	int town2;
	int cost;
	int time;

	Route() {}

	Route(int town1, int town2, int cost, int time)
		: town1(town1), town2(town2), cost(cost), time(time)
	{
	}
};

int N;
int C;
int V;
vector<Route> routes;

bool input(istream& in)
{
	if (!(in >> N)) return false;
	in >> C;
	in >> V;
	routes.resize(V);
	for (int i = 0; i < V; i++) in >> routes[i].town1;
	for (int i = 0; i < V; i++) in >> routes[i].town2;
	for (int i = 0; i < V; i++) in >> routes[i].cost;
	for (int i = 0; i < V; i++) in >> routes[i].time;
	return true;
}

struct RouteState
{
	int cost;
	int time;

	RouteState() {}

	RouteState(int cost, int time)
		: cost(cost), time(time)
	{
	}
};

struct less_RouteState
{
	bool operator()(const RouteState& a, const RouteState& b) {
		return a.time < b.time;
	}
};

int resolve()
{
	vector<vector<int>> route_indexes(N);
	for (int i = 0; i < V; i++) {
		route_indexes[routes[i].town1 - 1].push_back(i);
	}

	vector< vector<RouteState> > town_state(N);
	town_state[0].push_back(RouteState(0, 0));
	for (int src_town = 0; src_town < N; src_town++) {
		for (auto& src_town_state : town_state[src_town]) {
			for (auto& route_index : route_indexes[src_town]) {
				auto& route = routes[route_index];
				int next_cost = src_town_state.cost + route.cost;
				int next_time = src_town_state.time + route.time;
				if (next_cost <= C) {
					auto& dst_town_state = town_state[route.town2 - 1];
					bool can_add = true;
					for (auto& dst_town_state_item : dst_town_state) {
						if (next_cost > dst_town_state_item.cost && next_time > dst_town_state_item.time) {
							can_add = false;
							break;
						}
					}
					if (can_add) {
						for (size_t i = 0; i < dst_town_state.size(); i++) {
							if (dst_town_state[i].cost > next_cost && dst_town_state[i].time > next_time) {
								dst_town_state.erase(dst_town_state.begin() + i);
								i--;
							}
						}
						dst_town_state.push_back(RouteState(next_cost, next_time));
					}
				}
			}
		}
	}
	auto& last_town = town_state.back();
	auto ite = min_element(last_town.begin(), last_town.end(), less_RouteState());
	if (ite != town_state.back().end()) {
		return ite->time;
	}
	return -1;
}

int main(int argc, char **argv)
{
	if (argc > 1) {
		ifstream stream(argv[1]);
		while (input(stream)) {
			cout << resolve() << endl;
		}
	}
	else {
		while (input(cin)) {
			cout << resolve() << endl;
		}
	}

}