#include<bits/stdc++.h> using namespace std; long long timer[10001],value[10001],dp[1001][10001]={0}; int m,n; int main(){ cin>>m>>n; for(int i=1;i<=n;i++){ cin>>value[i]>>timer[i]; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp[i][j]=dp[i-1][j]; for(int k=1;k<=j/timer[i];k++){ dp[i][j]=max(dp[i][j],dp[i-1][j-timer[i]*k]+value[i]*k); } } } cout<<dp[n][m]<<endl; }