#include <iostream>
using namespace std;
int f[110][1010];
int a[1001];
int b[1001];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m; i++){
cin>>a[i];
cin>>b[i];
}
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
f[i][j]=f[i-1][j];
if(j-a[i]>=0&&f[i][j]<f[i-1][j-a[i]]+b[i]){
f[i][j]=f[i-1][j-a[i]]+b[i];
}
}
}
cout<<f[m][n];
return 0;
}
//真的题解