#include<iostream>
#include<cstdio>
using namespace std;
	int w[30]={0};
	int v[30]={0};
	int price[30001]={0};
	int ans[30001]={0};
	int m,n;
int main(){
	freopen("happy.in","r",stdin);
    freopen("happy.out","w",stdout);
	
	cin>>m>>n;

	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
		price[i]=w[i]*v[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=w[i];j--){
			ans[j]=max(ans[j],ans[j-w[i]]+price[i]);
		}
	}
	cout<<ans[m];
	return 0;
}