1379C - Choosing flowers - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int main()
{ll t;
cin>>t;
while(t--){
    ll m,n;
    cin>>m>>n;
    pair<ll,ll>p[n];
    ll arr[n],ps[n+1]={0};
    for(ll i=0;i<n;i++){
        ll x,y;
        cin>>x>>y;
        p[i]=make_pair(x,y);
        arr[i]=x;
    }
    sort(arr,arr+n);
    for(ll i=1;i<=n;i++){
        ps[i]=ps[i-1];
        ps[i]+=arr[i-1];
    }
    ll ans=0;
    for(ll i=0;i<n;i++){
        ll y=p[i].second;
        ll x=p[i].first;
        ll r=upper_bound(arr,arr+n,y)-arr;
        ll cnt=n-r;
        if(x<=y){
            cnt++;
        }
        if(cnt<=m){
            ll tot=ps[n]-ps[r];
            if(x<=y){
                tot+=x;
            }
            ll q=m-cnt;
            tot+=q*y;
            ans=max(ans,tot);
        }
        else{
            
            ans=max(ans,ps[n]-ps[n-m]);
        }
    }
    cout<<ans<<"\n";
    
}
    
   
}