ans = INF = 1<<30
gx,gy,n,f = map(int,input().split())
dp = [[INF]*(gy+1) for _ in range(gx+1)]
dp[0][0] = 0
for _ in range(n):
    x,y,c = map(int,input().split())
    for i in range(x,gx+1)[::-1]:
        for j in range(y,gy+1)[::-1]:
            dp[i][j] = min(dp[i][j],dp[i-x][j-y] + c)
for i in range(gx+1):
    for j in range(gy+1):
        ans = min(ans,dp[i][j] + f*(gx+gy-i-j))
print(ans)