/*TASK:inflateLANG:C++URL:*/#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#define ll long long#define N 10005int m,n,w[N],p[N],dp[N];using namespace std;int main() {	freopen("inflate.in","r",stdin);	freopen("inflate.out","w",stdout);	scanf("%d%d",&m,&n);	for(int i=1;i<=n;i++)		scanf("%d%d",&p[i],&w[i]);	for(int i=1;i<=n;i++)	for(int j=w[i];j<=m;j++)		if(dp[j-w[i]]+p[i]>dp[j])			dp[j]=dp[j-w[i]]+p[i];	int ans=0;	for(int i=0;i<=m;i++)	if(dp[i]>ans)ans=dp[i];	printf("%d\n",ans);	return 0;}