import sequtils template times*(n:int,body) = (for _ in 0.." .} proc scan(): int = while true: let k = getchar_unlocked() if k < '0': return result = 10 * result + k.ord - '0'.ord const INF = 1e10.int let gx = scan() let gy = scan() let n = scan() let f = scan() var dp = newSeqWith(gx+1,newSeqWith(gy+1,INF)) dp[0][0] = 0 n.times: let cx = scan() let cy = scan() let cost = scan() for x in 0..gx: for y in 0..gy: if x + cx > gx or y + cy > gy : continue dp[x+cx][y+cy] .min= dp[x][y] + cost var ans = INF for x in 0..gx: for y in 0..gy: ans .min= dp[x][y] + f * (gx - x + gy - y) echo ans