#include<bits/stdc++.h> using namespace std; int w[1000],val[1000]; int dp[1000][1000]; int main() { int t,m,res=-1; cin>>t>>m; for(int i=1; i<=m; i++) { cin>>w[i]>>val[i]; } for(int i=1; i<=m; i++) { for(int j=t; j>=0; j--) { if(j>=w[i]) { dp[i][j]=(dp[i-1][j-w[i]]+val[i]>dp[i-1][j]?dp[i-1][j-w[i]]+val[i]:dp[i-1][j]); } else { dp[i][j]=dp[i-1][j]; } } } cout<<dp[m][t]<<'\n'; return 0; }