paste bin

#include <cstdio>
#include <algorithm>
using std::max;

int main()
{
	int T,M,*Time,*Value,i,j;
    int dp[10001];
	scanf("%d %d",&T,&M);
	Time=new int [M+2];
	Value=new int [M+2];
	for(i=0;i<=T;i++)
		dp[i]=0;
    for(i=1;i<=M;i++)
		scanf("%d %d",&Time[i],&Value[i]);
	for(i=1;i<=M;i++)
	{
		for(j=T;j>=1;j--)
			if(j>=Time[i])
				dp[j]=max(dp[j],dp[j-Time[i]]+Value[i]);
	}
	printf("%d\n",dp[T]);
	return 0; 
}