import numpy as np

Gx, Gy, N, F = map(int, input().split())

dp = np.repeat(np.arange(Gx + 1)[None, :], Gy + 1, axis=0) \
     + np.repeat(np.arange(Gy + 1)[:, None], Gx + 1, axis=1)
dp *= F

for _ in range(N):
    X, Y, C = map(int, input().split())
    dp[Y:, X:] = np.minimum(dp[Y:, X:], dp[:Gy + 1 - Y, :Gx + 1 - X] + C)
print(dp[-1, -1])