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