#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;



struct item{
	int weight,value;
};



int main(){
	int t,m;
	cin>>t>>m;
	int dp[t+1];
	item a[m];
	memset(dp,0,sizeof(dp));
	for(int i=0;i<m;i++)
		cin>>a[i].value>>a[i].weight;
	for(int i=1;i<=m;i++)
		for(int j=a[i-1].weight;j<=t;j++)
			dp[j] = max(dp[j],dp[j-a[i-1].weight]+a[i-1].value);
	cout<<dp[t];
	return 0;
}