代码

#include<bits/stdc++.h>
using namespace std;

int t,m,ti[105],v[105],b[1005];
void knapasck(){
	for(int i=1;i<=m;i++){
		for(int j=t;j>=ti[i];j--){
			b[j]=max(b[j-ti[i]]+v[i],b[j]);
		}
	}
}
int main(){
    cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>ti[i]>>v[i];
	}
	knapasck();
	cout<<b[t]<<endl;
	//system("pause");
	return 0;
}