#include<bits/stdc++.h>
//#define int long long
using namespace std;
inline 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<<3)+(x<<1)+ch-48;ch=getchar();}
   return x*f;
}
void write(int x)
{
   if(x<0)putchar('-'),x=-x;
   if(x<10)putchar(x+'0');
   else write(x/10),putchar(x%10+'0');
}
const int N=2e6;
const int mod=1e9+7;
struct node{
	int u,v,w,nxt;
}mp[11000000];
int top;
int idx[N];
void add(int u,int v,int w){
	mp[++top]={u,v,w,idx[u]};
	idx[u]=top;
}
int X,Y,n,f;
int u[1000],v[1000],w[1000];
int id(int a,int b){
	return (a-1)*101+b;
}
struct nd{
	int id,z;
	bool operator < (const nd &p)const{
		return z>p.z; 
	}
};
bool vis[10000000];
priority_queue<nd>q;
int dis[10000000];
void dij(){
	memset(dis,0x3f,sizeof dis);
	dis[1]=0;
	q.push((nd){1,0});
	while(!q.empty()) {
		nd now=q.top();
		q.pop();
		if(vis[now.id])continue;
		vis[now.id]=1;
		for(int i=idx[now.id];i;i=mp[i].nxt){
			int v=mp[i].v;
			if(dis[v]>dis[now.id]+mp[i].w){
				dis[v]=dis[now.id]+mp[i].w;
				q.push((nd){v,dis[v]});
			}
		}
	}
	int zd=id(X,Y);
	int ans=INT_MAX;
	for(int i=0;i<=n;i++)
	ans=min(ans,dis[zd+101*101*i]);
	cout<<ans<<"\n";
}
signed main(){
//	freopen("crystal.in","r",stdin);
//	freopen("crystal.out","w",stdout);
	X=read(),Y=read(),n=read(),f=read();
	X++;
	Y++; 
	int all=101*101;
	for(int i=1;i<=n;++i)u[i]=read(),v[i]=read(),w[i]=read();
	for(int i=1;i<=101;++i){
		for(int j=1;j<=101;j++){
			int dd=id(i,j);
			if(i+1<=101)
			add(dd,id(i+1,j),f);
			if(j+1<=101)
			add(dd,id(i,j+1),f);
			for(int k=1;k<=n;k++){
				if(i+u[k]<=101&&j+v[k]<=101) add(dd,id(i+u[k],j+v[k])+all*k,w[k]);
			//	add(dd,dd+all*k,w[k]);
				if(i+1<=101) 
				add(dd+all*k,id(i+1,j)+all*k,f);
				if(j+1<=101)
				add(dd+all*k,id(i,j+1)+all*k,f);
				for(int l=1;l<k;l++)if(i+u[k]<=101&&j+v[k]<=101)add(dd+all*l,id(i+u[k],j+v[k])+all*k,w[k]);
			}
		}
	}
	dij();
    return 0;
}