#include<bits/stdc++.h>
using namespace std;
#define int unsigned int
#define MAX (int(1e18))
int dp[29][20005];
signed main(){
	int n,m;
	cin>>n>>m;
	int pp[268],pps[268];
	for(int i=1;i<=m;i++){
		int q,w;
		cin>>q>>w;
		pp[i]=q*w;
		pps[i]=q;
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(j>=pps[i]){
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-pps[i]]+pp[i]);
				
			} else{
				dp[i][j]=dp[i-1][j];
			}
		} 
	}
	cout<<dp[m][n];
	return 0;
}

https://www.luogu.com.cn/record/79139046

求助！为啥只有80分？