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