/contest/1379/problem/C
按a拍个序，然后枚举每种花
只多拿这一种
剩下的大于bi的aj的必须拿，因为可以通过少拿一个bi来换一个更大的aj，这样就可以把多拿每种花的最优情况求出来
注意处理一下ai>bi情况，这个时候数量有点小变化
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxl=3e5+10;int cas,k,cnt,tot;ll n,m,ans;struct node{ll a,b;bool operator < (const node &y)const{if(a==y.a)return b<y.b;return a<y.a;}}aa[maxl];ll suma[maxl],a[maxl],b[maxl];char s[maxl];bool in[maxl]; inline void prework(){scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++)scanf("%lld%lld",&aa[i].a,&aa[i].b);sort(aa+1,aa+1+m);for(int i=1;i<=m;i++){a[i]=aa[i].a,b[i]=aa[i].b;suma[i]=suma[i-1]+a[i];}} inline void mainwork(){if(n>m)ans=suma[m];elseans=suma[n];int ind,len;ll tmp;for(int i=1;i<=m;i++){ind=upper_bound(a+1,a+1+m,b[i])-a;if(ind<=i){len=min(m-ind+1,n);tmp=suma[m]-suma[m-len]+b[i]*(n-len);}else{len=min(m-ind+1,n-1);tmp=suma[m]-suma[m-len]+a[i]+b[i]*(n-len-1);}ans=max(ans,tmp);}}inline void print(){printf("%lld\n",ans);}int main(){int t=1;scanf("%d",&t);for(cas=1;cas<=t;cas++){prework();mainwork();print();}return 0;}
