#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[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[i][j] = (i+j)*F;
	rep(t,N){
		scanf("%d %d %d",&x,&y,&c);
		for (int i = H; i >= 0; i--)
			for (int j = W; j >= 0; j--) 
				if (i >= y && j >= x) dp[i][j] = min(dp[i][j],dp[i-y][j-x]+c);
	}
	printf("%d\n",dp[H][W]);
	return 0;
}