gx,gy,n,f=map(int,input().split())
wa=[[0,0,0]]+[list(map(int,input().split())) for i in range(n)]
inf=10**8
dp=[[[inf]*(gy+1) for i in range(gx+1)] for i in range(n+1)]
dp[0][0][0] = 0

for w in range(n+1):
    for i in range(gx+1):
        for j in range(gy+1):
            if dp[w][i][j] == inf:
                continue
            if w+1 < n+1:
                dp[w+1][i][j] = min(dp[w+1][i][j],dp[w][i][j])
            
            x,y,c=wa[w][0],wa[w][1],wa[w][2]
            if i + 1 <= gx:
                dp[w][i+1][j] = min(dp[w][i+1][j],dp[w][i][j]+f)
            if j + 1 <= gy:
                dp[w][i][j+1] = min(dp[w][i][j+1],dp[w][i][j]+f)
            if i < i+x <=gx and j < j+y <=gy and w+1 < n+1:
                dp[w+1][i+x][j+y] = min(dp[w+1][i+x][j+y],dp[w][i][j] + c)

ans=10**10
for i in range(n+1):
    ans=min(ans,dp[i][gx][gy])
print(ans)