#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
int f[10000000]={}; 
int m,n,c[10001],w[10001];
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++) cin>>w[i]>>c[i];
	for(int i=1;i<=n;i++){
		for(int j=m;j>=1;j--){
			for(int k=0;k<=j/w[i];k++){
				f[j]=max(f[j],f[j-w[i]*k]+k*c[i]);
			
			}
		}
	}
	cout<<f[m];
	return 0;
}