#include<bits/stdc++.h>
using namespace std;
#define int long long
#define bui __builtin_popcount
#define pii pair<int,int>
#define se second
#define fi first
#define mid (l+r>>1)
#define qwq cout<<"----------------------------------------------------------------------";
const int inf=1e18;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void prt(int x){
	if(x<0)putchar('-'),x=-x;
	if(x<10)putchar(x+'0');
	else prt(x/10),putchar(x%10+'0');
}
int ksm(int x,int y,int mod){
	if(y==0)return 1;
	int k=ksm(x,y/2ll,mod);
	if(y&1ll)return k*k%mod*x%mod;
	return k*k%mod;
}
const int N=1e6+5;
int gcd(int x,int y){return (y)?gcd(y,x%y):x;}
int max(int x,int y){return (x>y)?x:y;}
int min(int x,int y){return (x<y)?x:y;}
int x[105],y[105],g[105],f[105][105],n,m,p,q;
void sl(){
	memset(f,0x3f,sizeof(f));
	cin>>n>>m>>q>>p;
	f[0][0]=0;
	for(int i=1;i<=q;i++)cin>>x[i]>>y[i]>>g[i];
	for(int i=1;i<=q;i++){
		for(int j=n;j>=x[i];j--){
			for(int k=m;k>=y[i];k--){
				f[j][k]=min(f[j][k],f[j-x[i]][k-y[i]]+g[i]);
			}
		}
	}
	int ans=inf;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			ans=min(ans,f[i][j]+p*(n-i+m-j));
		}
	} 
	cout<<ans;
}
signed main(){
	int t=1;
//	cin>>t;
	while(t--)sl();
	return 0;
}