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