INF = 1e18
from collections import defaultdict

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

    def check(x, y):
        return 0 <= x <= Gx and 0 <= y <= Gy

    dp = defaultdict(lambda: INF)
    dp[(0, 0)] = 0

    for i in range(N):
        xi, yi, ci = map(int, input().split())
        ndp = defaultdict(lambda: INF)
        for k, v in dp.items():
            x, y = k
            # 不採用
            ndp[(x, y)] = min(ndp[(x, y)], v)
            nx, ny = x + xi, y + yi
            if check(nx, ny):
                ndp[(nx, ny)] = min(ndp[(nx, ny)], v + ci)
        dp = ndp

    ans = INF
    for k, v in dp.items():
        x, y = k
        sub = ((Gx - x) + (Gy - y))*F + v
        if sub < ans:
            ans = sub
    print(ans)
if __name__ == "__main__":
    main()