#include<bits/stdc++.h>
using namespace std;
int f[10000001];
int a[10001];
int b[10001];
int maxx(int i,int j){
	if(i>j)
	return i;
	return j; 
}
int main(){
	int m,n;
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=a[i];j--){
            for(int k=0;k*a[i]<=j;k++){
            	f[j]=maxx(f[j],f[j-k*a[i]]+k*b[i]);
            }
        }
    }
    int ans=0;
        for(int j=1;j<=m;j++){
            ans=maxx(ans,f[j]);
        }
    cout<<ans;
}

／／一脸蒙