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