#include<bits/stdc++.h>
using namespace std;
long long t,m,a[10010],b[10010],dp[10000010],s=1;
int main(){
	scanf("%d%d",&t,&m);
	for(int i = 1;i <= m;++i) scanf("%d%d",&a[i],&b[i]);
	for(int i = 1;i <= m;++i)
	for(int j = 1;j <= t;++j){
	while(j>=s*a[i]){
		dp[j]=max(dp[j],dp[j-s*a[i]]+s*b[i]);
		++s;
	}
	s=1;
	}
	cout<<dp[t];
	return 0;
}