gx, gy, n, f = map(int, input().split())
P = [list(map(int, input().split())) for _ in range(n)]

DP = [[(i + j) * f for i in range(gx + 1)] for j in range(gy + 1)]
for k in range(n):
    x, y, c = P[k]
    for i in range(gy, y - 1, -1):
        for j in range(gx, x - 1, -1):
            DP[i][j] = min(DP[i][j], DP[i - y][j - x] + c)
print(DP[-1][-1])