sub min{$_[$_[1]<$_[0]]}
($X,$Y,$N,$F)=glob<>;
for$y(0..$Y){
	for$x(0..$X){
		$_[$y][$x]=$F*($x+$y)
	}
}
for(<>){
	($dx,$dy,$c)=glob;
	for$y(0..$Y){
		for$x(0..$X){
			$_[$y+$dy][$x+$dx]=min($_[$y+$dy][$x+$dx],$_[$y][$x]+$c)
		}
	}
}
print$_[$Y][$X]