($N,$C,$V,$S,$T,$Y,$M)=<>;
@$_=(0,glob$$_)for S,T,Y,M;
$d[1][0]=_;
for(1..$N-1){
	for$v(1..$V){
		for$c(0..$C-$Y[$v]){
			if($d[$S[$v]][$c]){
				$_=\$d[$T[$v]][$c+$Y[$v]];
				$t=$d[$S[$v]][$c]+$M[$v];
				if(!$$_||$t<$$_){
					$$_=$t
				}
			}
		}
	}
}
@_=grep$_,@{$d[$N]};
print@_?(sort{$a-$b}@_)[0]:-1