#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int tj[10010],jz[10010];
int zjz[10010][10010];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>tj[i]>>jz[i];
	for(int i=1;i<=m;i++)
	{
		for(int j=n;j>=0;j--)
		{
			if(i>=tj[j])
			{
				zjz[i][j]=max(zjz[i-1][j-tj[i]]+jz[i],zjz[i-1][j]);
			}
			else zjz[i][j]=zjz[i-1][j];
		}
	}
	cout<<zjz[m][n];
	return 0;
	
}

刚学背包，还有点生疏qaq
提交代码千百遍，提交一遍虐一遍o((⊙﹏⊙))o