#include<bits/stdc++.h> using namespace std; long long V,n,c[10005],w[10005],dp[10005]; int main(){ cin>>V>>n; for(int i=1;i<=n;i++){ cin>>w[i]>>c[i]; } for(int i=1;i<=n;i++){ for(int j=V;j>=w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]]+c[i]); } } cout<<dp[V]; return 0; }