#include<bits/stdc++.h> #define int long long using namespace std; int a[10000005],b[10000005],dp[10000005]; signed main(){ int t,m; cin>>t>>m; for (int i = 1;i <= m;i++){ cin>>a[i]>>b[i]; } for (int i = 1;i <= m;i++){ for (int j = a[i];j <= t;j++){ dp[j] = max(dp[j],dp[j - a[i]] + b[i]); } } cout<<dp[t]<<endl; return 0; }