背包 代码见下：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+9;
int a[maxn],b[maxn];
long long dp[maxn*1000];
int main(){
	int t,m;
	cin >>t>>m;
	for(int i=1;i<=m;i++) cin>>a[i]>>b[i];
	for(int i=0;i<=t;i++) dp[i]=0;
	for(int i=1;i<=m;i++){
		for(int j=0;j<=t;j++){
			if(j<a[i]) dp[j]=dp[j];
			else dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
		}
	}
	cout <<dp[t];
}```