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