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