#include<bits/stdc++.h>
using namespace std;
int m,n,w[35],c[35],f[35][210];
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[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],c[i]+f[i-1][j-w[i]]);
			else
				f[i][j]=f[i-1][j];
		}	
	}
	cout<<f[n][m];
    return 0;
}
``