#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[30],c[30];
// w:每次的重量,c：价值 
int f[30][30];
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>w[i]>>c[i];
		c[i]*=w[i];
	}
	for(int i=1;i<=m;i++){//遍历物品数 
        for(int j=0;j<=n;j++){//遍历子背包 
            if(j>=w[i])//如果子背包能装下这件物品 
                f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
                //比较是不要这个物品好还是腾出这件物品的空间后好 
			else
			    f[i][j]=f[i-1][j]; //否则选上 
       }
    }
    cout<<f[m][n];
    
	return 0;
}