#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int V,n,w[N],c[N];
int mem[2020][2020];
int dfs(int deep,int r){
if(deep>n){
return mem[deep][r]=0;
}
if(mem[deep][r]!=-1)return mem[deep][r];
int t1=dfs(deep+1,r),t2=0;
if(r>=w[deep]){
t2=dfs(deep+1, r-w[deep])+c[deep];
}
return mem[deep][r]=max(t1,t2);
} int main(){
memset(mem, -1, sizeof(mem));
cin>>V>>n;
for(int i=1;i<=n;i++)cin>>w[i]>>c[i];
cout<<dfs(1,V);
return 0;
}