#10AC，其他点全WA

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,w[11451],v[11451],f[1101][1101];
signed main() {
	cin>>m>>n;
	for(int i = 1;i<=n;i++){
		cin>>w[i]>>v[i];
		v[i]*=w[i];
	}
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			if(j>=w[i]){
				f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);	
			}else{
				f[i][j]=f[i-1][j];
			}
		}
	} 
	cout<<f[n][]m];
}