#include #include #include #include using namespace std; #define INF 1930000000 const int MAX_N = 50; const int MAX_X = 100; const int MAX_Y = 100; int dp[MAX_X+1][MAX_Y+1];//50 * 10000 = 500,000 bool check[MAX_X+1][MAX_Y+1]; struct crystal{ int x; int y; int c; int safe; }; bool comp(const crystal &a, const crystal &b){ if(a.safe < b.safe) return true; return false; } int main(){ int gx,gy,N,F; cin >> gx >> gy >> N >> F; vector cry; int x, y, c, safe = 0; for(int j = 0; j < gx+1; j++){ for(int k = 0; k < gy+1; k++){ dp[j][k] = INF;//初期化 } } for(int i = 0; i < N;i++){ cin >> x >> y >> c; safe = (x+y)*F - c; if(safe > 0){ cry.push_back({x,y,c,safe}); } } if(cry.size() == 0){ cout << (gx+gy)*F << endl; return 0; } sort(cry.begin(),cry.end(),comp); dp[0][0] = 0; dp[cry[0].x][cry[0].y] = cry[0].c; dp[gx][gy] = cry[0].c + (gx- cry[0].x + gy - cry[0].y)* F; for(int i = 0; i < cry.size();i++){ for(int j = 0; j < gx+1; j++){ for(int k = 0; k < gy+1; k++){ check[j][k] = false;//初期化 } } for(int j = 0; j <= gx; j++){ for(int k = 0; k <= gy; k++){ if(j-cry[i].x >= 0 && k-cry[i].y >= 0){ if(check[j-cry[i].x][k-cry[i].y] == false){ dp[j][k] = min(dp[j][k], dp[j - cry[i].x][k - cry[i].y]+cry[i].c); check[j][k] = true; } } dp[gx][gy] = min(dp[gx][gy] ,dp[j][k]+(gx-j + gy-k)*F); } } } cout << dp[gx][gy] <