贪心、二分

场切，直接转化题目。有 $n$ 个长度为 $k$ 的不增数列，每个数列的前若干项形成等差数列，其余项为 $0$，现在要找出这些数列中前 $k$ 大数的和。

首先二分出第 $k$ 大的数，设其为 $x$，然后求出每个等差数列中大于 $x$ 的项的和设为 $s$，大于 $x$ 的项的数量设为 $w$。答案即为 $s+x(k-w)$。

时间复杂度 $O(n \log V)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int lim=1'000'000'000;
int n,k,a[200'005],b[200'005];
long long ans;
bool check(int x){
    long long res=k;
    for(int i=1;i<=n;i++) res-=max((a[i]-x+b[i]-1)/b[i],0);
    return res>=1;
}
long long calculate(int s,int d,int aim){
    if(aim>=s) return 0ll;
    int l=1,r=lim+5,ret=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(max(s-(mid-1ll)*d,0ll)<=aim) r=mid-1;
        else ret=mid,l=mid+1;
    }
    k-=ret;
    return (s+s-(ret-1ll)*d)*ret/2;
}
void solution(){
    cin>>n>>k,ans=0ll;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    int l=0,r=lim+5,aim=lim+5;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) aim=mid,r=mid-1;
        else l=mid+1;
    }
    for(int i=1;i<=n;i++) ans+=calculate(a[i],b[i],aim);
    ans+=1ll*k*aim;
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}