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