#include <iostream>
using namespace std;
int main()
{
int w, n, NegInf = -1;
cin >> w >> n;
int WeiCos[n][2], s[w + 1];
for(int i = 0; i < n; i++){
for(int j = 0; j < 2; j++){
cin >> WeiCos[i][j];
}
}
s[0] = 0;
for(int j = 1; j <= w; j++){
s[j] = NegInf;
}
for(int i = 0; i < n; i++){
for(int j = WeiCos[i][0]; j <= w; j++){
if(s[j - WeiCos[i][0]] != NegInf && s[j] < s[j - WeiCos[i][0]] + WeiCos[i][1]){
s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];
}
}
}
int maxS = 0;
for(int i = 1; i <= w; i++){
maxS = max(maxS, s[i]);
}
cout << maxS;
return 0;
}