// Problem: P1060 [NOIP2006 普及组] 开心的金明 // URL: https://www.luogu.com.cn/problem/P1060 // Author: Pengfei Xu #include<bits/stdc++.h> using namespace std; int main(){ int n,m; cin >> n >> m; vector<int> v(m+1),w(m+1),f(n+1);//v价格,w价值 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; }