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