#include<bits/stdc++.h> using namespace std; int w[10001],val[10001]; int dp[1005][10000]; 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]; } else { dp[i][j]=dp[i-1][j]; } } } cout<<dp[m][t]<<'\n'; return 0; }