for(int i=0; i<MAXN; i++)dp[i]=-INF;

dp[0] = 0;

for(int i=0; i<N; i++){

for(int j=0; j<=M; j++){

if(j+weight[i]<=M){

dp[j+weight[i]] = max(dp[j+weight[i]], dp[j]+gain[i]);

}

}

}

int ans = -1;

for(int i=0; i<=M; i++){

ans = max(ans, dp[i]);

}

fout<<ans<<endl;

fin>>M>>N;

for(int i=0; i<N; i++){

fin>>gain[i]>>weight[i];

}

work();

return 0;