Gx, Gy, N, F = map(int, input().split())
crystals = [tuple(map(int, input().split())) for _ in range(N)]

INF = float('inf')
dp = [[INF] * (Gy + 1) for _ in range(Gx + 1)]
dp[0][0] = 0  # Initial position

for x, y, c in crystals:
    # Create a new DP table for the next state
    new_dp = [row[:] for row in dp]
    for a in range(Gx + 1):
        for b in range(Gy + 1):
            if dp[a][b] == INF:
                continue
            # Calculate new position after using this crystal
            new_a = min(a + x, Gx)
            new_b = min(b + y, Gy)
            # Update the new_dp with the minimum cost
            if new_dp[new_a][new_b] > dp[a][b] + c:
                new_dp[new_a][new_b] = dp[a][b] + c
    # Update dp to new_dp after processing this crystal
    dp = new_dp

# Calculate the minimum cost considering walking fees
min_cost = INF
for a in range(Gx + 1):
    for b in range(Gy + 1):
        if dp[a][b] != INF:
            walk_x = max(Gx - a, 0)
            walk_y = max(Gy - b, 0)
            total_cost = dp[a][b] + (walk_x + walk_y) * F
            if total_cost < min_cost:
                min_cost = total_cost

print(min_cost)