#yuki_496

gx,gy,n,f=map(int,raw_input().split())
dp=[[0 for j in xrange(gx+1)]  for i in xrange(gy+1)]
for i in xrange(gy+1):
 for j in xrange(gx+1):
  dp[i][j]=(i+j)*f
for w in xrange(n):
 x,y,c=map(int,raw_input().split())
 for i in xrange(gy,y-1,-1):
  for j in xrange(gx,x-1,-1):
   if i>=y and j>=x:
    dp[i][j]=min(dp[i][j],dp[i-y][j-x]+c)
print dp[gy][gx]