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