#include <stdio.h>
#include <algorithm>

using namespace std;

#define range(i,a,b) for(int i=(a); i < (b); i++)
#define rep(i,n) range(i,0,n)

int dp[51][101][101];

int main(){
	int W,H,N,F,x,y,c;
	scanf("%d %d %d %d",&W,&H,&N,&F);
	rep(i,H+1) rep(j,W+1) dp[0][i][j] = (i+j)*F;
	rep(t,N){
		scanf("%d %d %d",&x,&y,&c);
		rep(i,H+1)
			rep(j,W+1){
				if (i >= y && j >= x) dp[t+1][i][j] = min(dp[t][i][j],dp[t][i-y][j-x]+c);
				else dp[t+1][i][j] = dp[t][i][j];
			}
		}
	printf("%d\n",dp[N][H][W]);
	return 0;
}