#include<bits/stdc++.h>
using namespace std;
const int maxn=100001;
int f[maxn],wei[maxn],weal[maxn],idx=0,sum[maxn];
int main()
{
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int wi,we;
		cin>>wi>>we;
		if(wi<=m)
		{
			wei[++idx]=wi;
			weal[idx]=we;
			sum[idx]+=sum[idx-1]+wei[idx];
		}		
	}
	for(int i=1;i<=idx;i++){
		int bound=max(wei[i],m-(sum[idx]-sum[i-1]));
			for(int j=m;j>=bound;j--){
				f[j]=max(f[j],f[j-wei[i]]+weal[i]);
			}
	}
	cout<<f[m];			  
}
来自重庆市某阴间中学的题库，把数据量扩大了两个数量级，淦！