import java.util.Arrays; import java.util.Scanner; public class Main { static Scanner in = new Scanner(System.in); public static void main(String[] args) { int Gx = in.nextInt(), Gy = in.nextInt(), N = in.nextInt(), F = in.nextInt(); if(N== 0){ System.out.println((Gx + Gy) * F); return; } int[] x = new int[N], y = new int[N], c = new int[N]; for (int i = 0; i < N; i++) { x[i] = in.nextInt(); y[i] = in.nextInt(); c[i] = in.nextInt(); } int[][] dp = new int[Gx + 1][Gy + 1]; for (int i = 0; i < Gx + 1; i++) { Arrays.fill(dp[i], Integer.MAX_VALUE); } dp[0][0] = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < Gx + 1; j++) { for (int k = 0; k < Gy + 1; k++) { if (j != 0) { dp[j][k] = Math.min(dp[j][k], dp[j - 1][k] + F); } if (k != 0) { dp[j][k] = Math.min(dp[j][k], dp[j][k - 1] + F); } if (j - x[i] >= 0 && k - y[i] >= 0) { dp[j][k] = Math.min(dp[j][k], dp[j - x[i]][k - y[i]] + c[i]); } } } } System.out.println(dp[Gx][Gy]); } }