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

ans = 1 << 30
for x in range(gx + 1):
    for y in range(gy + 1):
        ans = min(ans, dp[x][y] + (gx - x + gy - y) * f)
print(ans)