#include
using namespace std;
int main(){
int bw,tn,sum = 0;
int tweight[100],tvalue[100];
int f[100][100] = {0};//建立二维数组用来存储每一步的最优化
cin>>bw>>tn;
tweight[0] = 0;
tvalue[0] = 0;
for(int i = 1;i < tn+1;i++){
cin>>tweight[i]>>tvalue[i];
}
for(int i = 1;i <= tn;i++){
for(int j = 0;j <= bw;j++){
if(j < tweight[i])
f[i][j] = f[i - 1][j];
else
f[i][j] = max(f[i - 1][j - tweight[i]] + tvalue[i],f[i-1][j]);
}
}
cout<<f[tn][bw]<<endl;
return 0;
}