def f(h, w):
    return h * W + w

H, W, N, F = map(int, input().split())
H, W = H + 1, W + 1
X, Y, C = [0] * N, [0] * N, [0] * N
for i in range(N):
    X[i], Y[i], C[i] = map(int, input().split())

inf = 10 ** 18
pre = [inf] * (H * W)
pre[0] = 0

for i in range(N):
    dp = [inf] * (H * W)
    for a in range(H):
        for b in range(W):
            dp[f(a,b)] = min(dp[f(a,b)], pre[f(a,b)])
            x = a + X[i]
            y = b + Y[i]
            if x < 0 or x > H - 1 or y < 0 or y > W - 1:
                continue
            dp[f(x,y)] = min(dp[f(x,y)], pre[f(a,b)] + C[i])

    dp, pre = pre, dp

ans = inf
for i in range(H):
    for j in range(W):
        ans = min(ans, pre[f(i,j)] + F * (H + W - 2 - i - j))

print(ans)
# print(pre)