#include<bits/stdc++.h> using namespace std; int dp[1010],t,m; int main(){ cin>>t>>m; for(int i=1;i<=m;i++){ int ti,vi; cin>>ti>>vi; for(int j=t;j>=1;j--) if(j>=ti) dp[j]=max(dp[j],dp[j-ti]+vi); cout<<endl; } cout<<dp[t]; return 0; }