#include<iostream> using namespace std; int w[10001],c[10001],dp[10001]; int main(){ int t,m; cin>>t>>m; for(int i=1;i<=m;i++){ cin>>w[i]>>c[i]; } for(int i=1;i<=m;i++){ for(int j=t;j>=w[i];j--){ dp[j]=max(dp[j-w[i]]+c[i],dp[j]); } } cout<<dp[t]<<endl; return 0; }