题解：CF1379C
__phiu
·
·
题解
Pro
## Sol
首先发现一个基本事实是：我们至多让一种物品选很多次。
证：因为如果两个物品同时选多次，那么一定是两个都被选过一次，那么用 $b_i$ 更大的去替换另一个一定不劣。
那么我们可以直接枚举被选多次的那个物品 $k$，那么考虑其它物品，如果它们被选一次，那么一定是 $a_i > b_k$，这样做是 $O(n^2)$ 的，考虑按 $a_i$ 进行排序，二分找到第一个比当前枚举位置小的，那么前面的全部选择，用前缀和简单维护就好了。
## Code
```cpp
#include<bits/stdc++.h>
#define mp make_pair
#define For(i,a,b,c) for(int i=a;i<=b;i+=c)
#define Rof(i,a,b,c) for(int i=a;i>=b;i-=c)
#define pb push_back
#define pii pair<int,int>
using namespace std;
inline int read(){
char c=getchar();
int x=0,f=1;
while(c<'0' or c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0' and c<='9')
x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int N=1e5+50;
struct node {
int a,b;
bool operator < (const node &p ) const {
return a>p.a ;
}
}a[N];
int t;
long long sum[N] ;
signed main(){
t = read() ;
while(t--) {
int m = read() ;
int n = read() ;
for(int i=1;i<=n;i++) {
a[i].a = read() , a[i].b = read() ;
}
sort(a+1,a+n+1) ;
for(int i=1;i<=n;i++) sum[i] = sum[i-1] + a[i].a;
long long ans = 0 ;
for(int i=1;i<=n;i++) {
int l = 1, r = n;
while(l<=r) {
int mid = l+r >>1 ;
if(a[mid].a>=a[i].b)
l=mid+1;
else
r=mid-1;
}
l--;//第一个小的，选的是 1 ~ l-1
if(l>=m)
ans=max(ans,sum[m]);//如果比它大的超过选的个数，就不选它了
else if(l >= i ) ans = max(ans,sum[l]+1ll*(m-l)*a[i].b) ;//如果自己的第一次已经选了就不用额外选一次
else ans = max(ans,sum[l]+a[i].a+1ll*(m-l-1)*a[i].b);//第一次没被选先选一次再累加其他贡献
}
printf("%lld\n",ans);
}
return 0;
}
```