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(); 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[N + 1][Gx + 1][Gy + 1]; for(int i = 0; i < Gx + 1; i++){ for(int j = 0; j < Gy + 1; j++){ dp[0][i][j] = (i + j) * F; } } for(int i = 1; i < N + 1; i++){ for(int j = 0; j < Gx + 1; j++){ for(int k = 0; k < Gy + 1; k++){ if(j == 0 && k == 0){ dp[i][j][k] = dp[i - 1][j][k]; } if(j != 0){ dp[i][j][k] = Math.min(dp[i - 1][j][k], dp[i - 1][j - 1][k] + F); } if(k != 0){ dp[i][j][k] = Math.min(dp[i - 1][j][k], dp[i - 1][j][k - 1] + F); } if(j - x[i - 1] >= 0 && k - y[i - 1] >= 0){ dp[i][j][k] = Math.min(dp[i - 1][j][k], dp[i - 1][j - x[i - 1]][k - y[i - 1]] + c[i - 1]); } } } } System.out.println(dp[N][Gx][Gy]); } }