import heapq

INF = 1 << 60

gx, gy, n, f = map(int, input().split())

dp = {}
dp[(0, 0)] = 0
for _ in range(n):
  dx, dy, dc = map(int, input().split())
  ndp = {}
  for cur, c in dp.items():
    cx, cy = cur
    ndp[(cx, cy)] = min(ndp.get((cx, cy), INF), c)
    nx = cx + dx
    ny = cy + dy
    if nx <= gx and ny <= gy:
      ndp[(nx, ny)] = min(ndp.get((nx, ny), INF), c + dc)
  dp = ndp

ans = INF
for diff, cost in dp.items():
  dx, dy = diff
  ans = min(ans, cost + (abs(gx - dx) + abs(gy - dy)) * f)

print(ans)