#include using namespace std; typedef long long ll; #define all(x) (x).begin(),(x).end() const int mod=1000000007,MAX=1<<17; const ll INF=1LL<<45; int main(){ int x,y,N; ll F;cin>>x>>y>>N>>F; vector A(N),B(N),C(N); for(int i=0;i>A[i]>>B[i]>>C[i]; } ll dp[x+1][y+1]; for(int i=0;i=0;i--){ for(int j=y;j>=0;j--){ if(i-A[k]<0) continue; if(j-B[k]<0) continue; dp[i][j]=min(dp[i][j],dp[i-A[k]][j-B[k]]+C[k]); } } } ll ans=INF; for(int i=0;i