#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll dp[30005][30]={1};
//dp数组，注意dp[0]=1 
ll v[30],p[30];
ll c[30];
//c用来存物品价值 
int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>v[i]>>p[i];
		c[i]=v[i]*p[i];
		//物品价值=重量*重要度 
	}
	for(int i=1;i<=m;i++){
		for(int j=n;j>=0;j--){
			if(v[i-1]>j) dp[i][j]=dp[i-1][j];
			//选不了只能运算不选的方案 
			else dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+c[i-1]);
			//选得了则比较大小 
		}
	}
	cout<<dp[m][n]<<"\n";
	//输出即可 
	return 0;
}

看上去是道特殊背包，实际上是特殊的01背包😕