题意：
有m种花，每种的数量无限，每朵花有a(i)和b(i)。
现在你需要挑出n朵花，第一次挑选某种花的时候，权值增加a(i)，之后每次都只增加b(i)
问挑选n朵花能得到的最大权值是多少。
数据范围：m<=1e5，n<=1e9
解法：
如果某种花要购买多次，那么之后每次增加的权值是b(i)，
一种想法是选出b(i)最大的，如果买超过一朵就都买这种花，
贪心一下，买这个b(i)之前，把所有大于这个b(i)的其他a(i)都买下来。
但是这种做法有一个问题，就是最大的b(i)本身对应的a(i)可能很小，
例如：
2 2
11 9
1 10
这组数据第二种花的b(i)很大，但是a(i)很小，就不成立了。
但是从上面的想法可以推测出，最多只有一种花买超过一朵，
那么枚举这个超过一朵的花，优先买大于b(i)的其他a(i)花，然后剩下的全买这种就行了，对答案取max
找大于b(i)的花可以用排序+二分做
需要注意的点：
如果a(i)>b(i)，那么买大于b(i)的花的时候已经买了当前a(i)
如果a(i)<=b(i)，那么还需要多花费一次机会买当前a(i)
code：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=1e5+5;
struct Node{int a,b;
}a[maxm];
int sum[maxm];
int c[maxm];
int n,m;
bool cmp(int a,int b){return a>b;
}
signed main(){int T;cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=m;i++){cin>>a[i].a>>a[i].b;c[i]=a[i].a;}sort(c+1,c+1+m,cmp);//从大到小排序for(int i=1;i<=m;i++){sum[i]=sum[i-1]+c[i];}int ans=0;for(int i=1;i<=m;i++){//枚举最后b[i]买的是哪种int temp=0;int remain=n;//二分找>b[i]的int l=1,r=m;int p=-1;while(l<=r){int mid=(l+r)/2;if(c[mid]>a[i].b){p=mid,l=mid+1;}else{r=mid-1;}}if(p==-1){//没有>b[i]的,那么全买这一种ans=max(ans,a[i].a+(n-1)*a[i].b);continue;}//if(p>n)p=n;temp+=sum[p];remain-=p;if(a[i].a>=c[p]){temp+=a[i].b*remain;}else{if(remain){temp+=a[i].a;remain--;temp+=a[i].b*remain;}}//ans=max(ans,temp);}cout<<ans<<endl;}return 0;
}