题解：AT_abc415_g [ABC415G] Get Many Cola

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5;
int n,m,c[305],dp[N+5],x,y,ans; 
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		c[x]=max(c[x],y);//花费同样的瓶子，得到的可乐不一定一样，此时取最大 
	}
	for(int i=1;i<=300;i++)//直接dp会超时，考虑大贪心，小dp 
		for(int j=i;j<=N;j++)//确保有i个瓶子兑换 
			dp[j]=max(dp[j],dp[j-(i-c[i])]+i);
	if(n<N){//n太小以致于可以直接dp 
		cout<<dp[n];
		return 0;
	}
	for(int i=1;i<=300;i++){//大贪心,枚举每种兑换方案 
		int cs=(n-N+i)/(i-c[i]);//+i是为了防止下面n-cs*(i-c[i])超过N，因为我们dp只到了N 
		ans=max(ans,cs*i+dp[n-cs*(i-c[i])]);//cs*i是直接用i换c[i]的收益，dp[...]是dp的收益，然后对于每个兑换方案取最大值 
	}
	cout<<ans;
	return 0;
}