#include<bits/stdc++.h> using namespace std; const int M=10010,N=10010; int dp[N][M]; int main(){ int m,n; cin>>m>>n; for(int i=1;i<=n;i++){ int si,ti; cin>>si>>ti; for(int j=1;j<=m;j++){ for(int k=0;k*ti<=j;k++){ dp[i][j]=max(dp[i][j],dp[i-1][j-k*ti]+k*si); } } } cout<<dp[n][m]<<endl; return 0; }