#include<bits/stdc++.h>
using namespace std;
int dp[20005];
int main(){
	int n,maxw;scanf("%d%d",&maxw,&n);
	while(n--){
		int v,w;scanf("%d%d",&v,&w);
		for(int i=maxw;i>=v;i--) dp[i]=max(dp[i-v]+w,dp[i]);
	}
	printf("%d",dp[maxw]);
	return 0;
}

/**************************************************************
	Problem: 1282
	User: liangshinan
	Language: C++
	Result: Accepted
	Time:41 ms
	Memory:2156 kb
****************************************************************/