#include #include #include using namespace std; 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 i = 0; i < N;i++){ cin >> x >> y >> c; safe = (x+y)*F - c; if(safe > 0){ cry.push_back({x,y,c,safe}); } } sort(cry.begin(),cry.end(),comp); /* for(auto e : cry){ cout << e.x << "," << e.y << "," << e.c << "," << e.safe << endl; }*/ int tcost = 0,px=0,py=0; for(int i = 0; i < N; i++){ if(px + cry[i].x <= gx && py + cry[i].y <= gy){ px += cry[i].x; py += cry[i].y; tcost += cry[i].c; } } tcost += (gx-px)*F; tcost += (gy-py)*F; cout << tcost << endl; return 0; }