#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]; int main(){ int gx,gy,N,F; cin >> gx >> gy >> N >> F; int x,y,c; for(int j = 0; j < gy+1; j++){ for(int k = 0; k < gx+1; k++){ dp[j][k] = F*(k+j);//初期化 //cout << dp[j][k] << " "; } // cout << endl; } for(int t = 0; t < N; t++){ cin >> x >> y >> c; for(int i = 0; i < gy+1; i++){ for(int j = 0; j < gx+1; j++){ if(i - y >= 0 && j - x >= 0){ dp[i][j] = min(dp[i][j],dp[i-y][j-x]+c); } } } } /* for(int j = 0; j < gy+1; j++){ for(int k = 0; k < gx+1; k++){ cout << dp[j][k] << " "; } cout << endl; } */ cout << dp[gy][gx] << endl; return 0; }