#include<algorithm>
#include<iostream>
#include<array>
#include<type_traits>

constexpr std::size_t road_max=1500;
constexpr std::size_t infinity=9999999;

template<class T,std::size_t size>
struct Setter{
	explicit Setter()=default;
	struct decrement;

	template<class Tag=std::nullptr_t>
	void set(const std::size_t in)
	{
		std::cin>>ar_[in];
		if(std::is_same<Tag,Setter::decrement>::value)--ar_[in];
	}

	T& operator[](std::size_t in){return ar_[in];}
	std::array<T,size> ar_;
};

int main()
{
	std::size_t N{},C{},V{};
	std::array<std::array<std::size_t,301>,50> ct{};
	for(auto& ar:ct)std::fill(ar.begin(),ar.end(),infinity);

	using Set=Setter<std::size_t,road_max>;
	Set S{},T{},Y{},M{};

	std::cin>>N>>C>>V;

#define REP_V for(std::size_t i=0; i<V; ++i)	
	REP_V S.set<Set::decrement>(i); REP_V T.set<Set::decrement>(i);
	REP_V Y.set<>(i); REP_V M.set<>(i);
	
	ct[0][C]=0;
	for(std::size_t i=0; i<N; ++i)
		for(std::size_t j=0; j<=C; ++j)
			for(std::size_t k=0; k<V; ++k)
				if(S[k]==i and Y[k]<=j)
					ct[T[k]][j-Y[k]]=std::min(ct[T[k]][j-Y[k]],ct[i][j]+M[k]);

	std::size_t rs=infinity;
	for(std::size_t i=0; i<=C; ++i)rs=std::min(rs,ct[N-1][i]);
	std::cout<<static_cast<signed>((rs==infinity?-1:rs))<<std::endl;
}