#include<bits/stdc++.h>
using namespace std;
int m,n,ans;
int w[30005],c[30005];
int last[30005]; //上一个f[i]
int f[30005]; //f[i]表示在背包容量有i时的最大价值 
int main(){ 
    cin>>m>>n;
    for(int i=1;i<=n;i++){
    	cin>>w[i]>>c[i];
    	c[i]=c[i]*w[i];
	}
    for(int i=1;i<=n;i++){
    	for(int j=0;j<=m;j++){
    		if(j>=w[i])f[j]=max(last[j],last[j-w[i]]+c[i]);
    		else f[j]=last[j];
    		for(int k=0;k<=m;k++)
			    last[k]=f[k];
		}
	}
	for(int i=1;i<=m;i++)ans=max(ans,f[i]);
	cout<<ans;
	return 0; 
}