#include<bits/stdc++.h> using namespace std; int w[1000],v[1000],f[50000]; int n,m; int main(){ cin>>m>>n; for(int i=1;i<=n;i++){ cin>>v[i]>>w[i]; w[i]*=v[i]; } for(int i=1;i<=n;i++){ for(int j=m;j>=v[i];j--){ if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]); } } cout<<f[m]<<endl; return 0; }

#include<bits/stdc++.h> using namespace std; int n,m; int ans=0; int a[10006],b[10006]; void work(int dep,int v,int p){ if(v>n)return; if(dep>m){ ans=max(ans,p); return; } work(dep+1,v+a[dep],p+a[dep]*b[dep]); work(dep+1,v,p); } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a[i]>>b[i]; } work(1,0,0); cout<<ans<<endl; return 0; }

#include<bits/stdc++.h> using namespace std; int w[1000],v[1000],f[50000]; int n,m; int main(){ cin>>m>>n; for(int i=1;i<=n;i++) { cin>>v[i]>>w[i]; w[i]*=v[i]; } for(int i=1;i<=n;i++) { for(int j=m;j>=v[i];j--) { if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]); } } cout<<f[m]<<endl; return 0; }