#include<iostream>
#define N 1000
using namespace std;
int a[N],b[N],dp[N][N],n,m;//dp[容量][数目]
//  重量 价值 
int main(){
	cin>>n>>m;//容量 数目 
	for(int i=1;i<=m;i++)cin>>a[i]>>b[i];
	for(int i=1;i<=m;i++)//i=数目 
		for(int j=1;j<=n;j++)//j=容量
			for(int k=n/a[i];k>-1;k--)
				dp[j][i]=max(dp[j][i-1],k*b[i]+dp[j-k*a[i]][i-1]);
	cout<<dp[n][m];
	return 0;
}