using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (gx, gy, n, f) = (c[0], c[1], c[2], c[3]); var map = NArr(n); var dp = new int[gx + 1, gy + 1]; var INF = int.MaxValue / 2; for (var x = 0; x <= gx; ++x) for (var y = 0; y <= gy; ++y) dp[x, y] = INF; dp[0, 0] = 0; for (var i = 0; i < n; ++i) for (var x = gx; x >= 0; --x) for (var y = gy; y >= 0; --y) if (dp[x, y] != INF) { if (x + map[i][0] > gx || y + map[i][1] > gy) continue; dp[x + map[i][0], y + map[i][1]] = Math.Min(dp[x + map[i][0], y + map[i][1]], dp[x, y] + map[i][2]); } var ans = INF; for (var x = 0; x <= gx; ++x) for (var y = 0; y <= gy; ++y) ans = Math.Min(ans, dp[x, y] + (gx - x + gy - y) * f); WriteLine(ans); } }