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 + 1 - y):
        for j in range(gx + 1 - x):
            DP[i + y][j + x] = min(DP[i + y][j + x], DP[i][j] + c)
print(DP[-1][-1])