#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int ll; typedef pair pii; typedef tuple t3; using namespace std; #define MAX_N 110 int dp[MAX_N][MAX_N][MAX_N]; int main(){ int gx,gy,n,f; cin >> gx >> gy >> n >> f; for(int i = 0;i <= n;i++) { for(int y = 0;y <= gy;y++) { for(int x = 0;x <= gx;x++) { dp[i][y][x] = (x + y) * f; } } } for(int i = 0;i < n;i++) { int sx,sy,sc; cin >> sx >> sy >> sc; for(int y = 0;y <= gy;y++) { ll ny = sy + y; if(ny > gy) { continue; } for(int x = 0;x <= gx;x++) { ll nx = sx + x; if(nx > gx) { continue; } dp[i+1][ny][nx] = min(dp[i+1][ny][nx], dp[i][y][x] + sc); } } for(int y = 0;y <= gy;y++) { for(int x = 0;x <= gx;x++) { if(x > 0) { dp[i+1][y][x] = min(dp[i+1][y][x], dp[i+1][y][x-1] + 1); } if(y > 0) { dp[i+1][y][x] = min(dp[i+1][y][x], dp[i+1][y-1][x] + 1); } } } } cout << dp[n][gy][gx] << endl; return 0; }