#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5,MAXB=2e7;
#define ll long long
int n,m,a[10001],v[10001],w[100001];
int main() {
	cin>>m>>n;//m为背包重量，n为有n种物品
	for(int i=1; i<=n; i++) {
		cin>>v[i]>>w[i];//wi为重量，vi为价值
		w[i]*=v[i];
	}
	for(int i=1; i<=n; i++)
		for(int j=m; j>=w[i]; j--)
			if(j>=v[i])
				a[j]=max(a[j],a[j-w[i]]+v[i]);
	cout<<a[m];
	return 0;
}