($gx,$gy,$n,$f)=glob<>;
@a=(<>,"0 1 $f","1 0 $f");
for$y(0..$gy){
	for$x(0..$gx){
		$d{$y,$x}=$x+$y&&1e9;
		for(@a){
			($xi,$yi,$ci)=glob;
			$xs=$x-$xi;
			$ys=$y-$yi;
			$d{$y,$x}=$d{$ys,$xs}+$ci if $ys>=0 && $xs>=0 && $d{$y,$x}>$d{$ys,$xs}+$ci;
		}
	}
}
print$d{$gy,$gx}