#include <iostream> //0-1背包

using namespace std;

const int max_m=105,max_w=10005;

int main()

{

int c,m,v[max_m],w[max_m],dp[max_w];

cin>>c>>m;

for(int i=1;i<=m;++i)

cin>>w[i]>>v[i];

for(int i=1;i<=m;++i)

for(int j=c;j>=w[i];--j)

dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

cout<<dp[c]<<endl;

return 0;

}