题解

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int dp[N][N];
int n;
int main(){
	int W,N;
	cin>>W>>N;
	vector<int> w(N),v(N);
	for(int i=0;i<N;i++){
		cin>>w[i]>>v[i];
	}
	vector<vector<int> > dp(N+1,vector<int>(W+1,0));
	for(int i=1;i<=N;i++){
		for(int j=0;j<=W;j++){
			if(j>=w[i-1]){
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
			}
			else{
				dp[i][j]=dp[i-1][j];
			}
		}
	}
	cout<<dp[N][W]<<endl;
	return 0;
}