#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[110][110];
int dx[55],dy[55],c[55],h,w,n,f;
signed main() {
	cin>>h>>w>>n>>f;
	for(int i=1;i<=n;i++)cin>>dx[i]>>dy[i]>>c[i];
	memset(dp,0x3f,sizeof dp);
	for(int x=0;x<=h;x++)
		for(int y=0;y<=h;y++) dp[x][y]=(x+y)*f;
	for(int i=1;i<=n;i++) {
		for(int x=h;x>=0;x--)
			for(int y=w;y>=0;y--) {
				if(x>0) dp[x][y]=min(dp[x][y],dp[x-1][y]+f);
				if(y>0) dp[x][y]=min(dp[x][y],dp[x][y-1]+f);
				if(x>=dx[i]&&y>=dy[i]) dp[x][y]=min(dp[x][y],dp[x-dx[i]][y-dy[i]]+c[i]); 
			}
	}
	cout<<dp[h][w]<<"\n";
	return 0;
}