import java.io.*; import java.math.BigInteger; import java.util.*; /** * Created by btk on 2017/03/16. */ public class Main { static FastScanner in; static PrintWriter out; static void solve() { int Gr = in.nextInt(); int Gc = in.nextInt(); int N = in.nextInt(); int F = in.nextInt(); int[] x=new int[N]; int[] y=new int[N]; int[] c=new int[N]; for (int i = 0; i < N; i++) { x[i] = in.nextInt(); y[i] = in.nextInt(); c[i] = in.nextInt(); } int[][] d=new int[212][212]; for (int i = 0; i < 212; i++) { Arrays.fill(d[i],11234567); } d[0][0] = 0; for (int i = 0; i <= Gr; i++) { for (int j = 0; j <= Gc; j++) { d[i+1][j] = Math.min(d[i+1][j],d[i][j]+F); d[i][j+1] = Math.min(d[i][j+1],d[i][j]+F); } } for (int k = 0; k < N; k++) { for (int i = Gr; i >= x[k]; i--) { for (int j = Gc; j >= y[k]; j--) { d[i][j] = Math.min(d[i][j],d[i-x[k]][j-y[k]]+c[k]); } } } out.println(d[Gr][Gc]); } public static void main(String[] args){ in = new FastScanner(); out = new PrintWriter(System.out); solve(); out.flush(); out.close(); } } class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; }else{ ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;} public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();} public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while(isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while(true){ if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; }else if(b == -1 || !isPrintableChar(b)){ return minus ? -n : n; }else{ throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { long nl = nextLong(); if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public double nextDouble() { return Double.parseDouble(next());} } class Pair implements Comparable { BigInteger a; int b; public Pair(BigInteger a, int b) { this.a = a; this.b = b; } //(a,b)が一致 @Override public boolean equals(Object o) { if (o instanceof Pair) { Pair p = (Pair) o; return a == p.a && b == p.b; } return super.equals(o); } //辞書順比較 @Override public int compareTo(Pair o) { if (!a.equals(o.a)) { return a.compareTo(o.a); } return Integer.compare(b,o.b); } }