#include<bits/stdc++.h> using namespace std; const int maxn=30005; int f[maxn]; int main(){ int n,m; cin>>n>>m; vector<int> v(m+1),w(m+1),f(n+1); for (int i=1,p;i<=m;++i){ cin>>v[i]>>p; w[i]=v[i]*p; } for (int i=1;i<=m;i++){ for (int j=n;j>=v[i];j--){ f[j]=max(f[j],w[i]+f[j-v[i]]); } cout<<f[n]<<endl; } }