#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LONG_INF 10000000000000000 #define MAX_MOD 1000000007 #define REP(i,n) for(long long i = 0;i < n;++i) long long dp[300][300][300] = {}; int main() { int gx, gy, n, f; cin >> gx >> gy >> n >> f; for (int i = 0;i <= 100;++i) { for (int q = 0;q <= 100;++q) { for (int j = 0;j <= 50;++j) { dp[i][q][j] = 100000000; } } } dp[0][0][0] = 0; for (int t = 0;t < n;++t) { long long x, y, c; cin >> x >> y >> c; for (int i = 0;i <= gx;++i) { for (int q = 0;q <= gy;++q) { dp[i + x][q + y][t + 1] = min(dp[i + x][q + y][t + 1], dp[i][q][t] + c); dp[i][q][t+1] = min(dp[i][q][t + 1], dp[i][q][t]); } } } long long ans = 100000000; for (int i = 0;i <= gx;++i) { for (int q = 0;q <= gy;++q) { ans = min(ans, (gx - i + gy - q)*f + dp[i][q][n]); } } cout << ans << endl; return 0; }