#include<bits/stdc++.h>
using namespace std;
long long dp[10000005];
long long w[1000005],v[1000005];
int main(){
	int t,m;
	scanf("%d%d",&t,&m);
	int mi=0x3f3f3f3f;
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",w+i,v+i);
		if(w[i]<mi)mi=w[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=t;j>=0;j--){
			for(int k=0;k<=t/mi+1;k++){
				
				if(j>=w[i]*k){
					dp[j]=max(dp[j-w[i]*k]+v[i]*k,dp[j]);
				}
				else break;
			}
			
		}
	}
	printf("%lld",dp[t]);
	
	
	return 0;
}