Preface：
这是生平第一道现场 AC 的 arc E，也生平第一次经历了 performance (ge 2800)，甚至还生平第一次被 hb 拉到会议里讲题，讲的就是这个题，然鹅比较尬的一点是我不知道腾讯会议开了白板之后不能看到电脑，导致我的 typora 没人能看到……所以就暂且把我 typora 的内容整了整改成了一篇题解（
题意：
- 有 (n) 种零食，第 (i) 种零食有 (a_i) 个。
- 有 (m) 个人领这些零食，第 (i) 个人最多领 (b_i) 个同种零食
- 第 (i) 个人领零食的总数不能超过 (c_i)
- 求最多能分出去多少零食
- (n,mle 2 imes 10^5,a_ile 10^{12},b_ile 10^7)
首先考虑网络流建图，我们新建一个源点 (S) 和汇点 (T)，然后考虑将零食看作左部点 (X_i)，人看作右部点 (Y_i)，那么我们显然可以建出以下几类边：
- 对每个 (iin[1,n]) 连边 (S o X_i)，容量 (a_i)
- 对每个 (iin[1,n],jin[1,m]) 连边 (X_i o Y_j)，容量 (b_j)
- 对每个 (iin[1,m]) 连边 (Y_i o T)，容量 (c_i)
然后跑最大流就是答案。不过显然直接建图复杂度爆炸——甚至连图都存不下，因此考虑这样一个套路：使用最大流&最小割定理转化为最小割问题。也就是我们要割掉权值最小的边集使得 (S,T) 不连通。下记 (S o X_i) 为第一类边，(X_i o Y_j,Y_i o T) 分别记作第二、三类边。
这个问题就可以贪心求解了。考虑枚举保留多少个一类边，记作 (x)，那注意到此题的一个性质，所有左部点（也就是 (X_i)）在我们钦定割/不割掉与 (S) 相连的边后就是等价的了，也就是说只有切掉的个数有意义，具体切的是哪些边对后面（也就是切二、三类边的代价）的计算没有影响。因此我们肯定会贪心地割掉最小的 (n-x) 条 一类边，排序+前缀和求解即可。接下来考虑割掉二、三类边的代价，对于一个 (Y_j)，目前有用的边肯定只剩下 (x) 条与 (Y_j) 相连的二类边和 (Y_j) 连向汇点的三类边，显然要么二类边全删，要么三类边全删，因此删掉与 (j) 有关的边的代价是 (min(c_j,b_j·x))。将所有右部点按照 (dfrac{c_j}{b_j}) 排序后 (min) 取到 (c_j) 的部分一定是一段前缀，(min) 取到 (b_j·x) 的部分肯定是对应部分的一个补集，也就是一段后缀。我们在枚举 (x) 的过程中 two pointers 找出这段前缀，然后预处理出 (b,c) 的前缀和即可 (mathcal O(1)) 计算贡献。
时间复杂度 (nlog n)（如果 (n,m) 视作同阶），注意精度，直接比较 double 可能会获得 ( ext{AC} imes26, ext{WA} imes1) 的好成绩。
const int MAXN=2e5;
int n,m,ord[MAXN+5];
ll a[MAXN+5],b[MAXN+5],c[MAXN+5];
ll suma[MAXN+5],sumb[MAXN+5],sumc[MAXN+5];
bool cmp(int x,int y){return 1ull*c[x]*b[y]<1ull*b[x]*c[y];}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=m;i++) scanf("%lld",&b[i]);
for(int i=1;i<=m;i++) scanf("%lld",&c[i]);
for(int i=1;i<=m;i++) ord[i]=i;
sort(a+1,a+n+1);sort(ord+1,ord+m+1,cmp);
for(int i=1;i<=n;i++) suma[i]=suma[i-1]+a[i];
for(int i=1;i<=m;i++) sumb[i]=sumb[i-1]+b[ord[i]];
for(int i=1;i<=m;i++) sumc[i]=sumc[i-1]+c[ord[i]];
ll res=1e18;
for(int i=0;i<=n;i++){
int l=1,r=m,p=0;
while(l<=r){
int mid=l+r>>1;
if(1ll*b[ord[mid]]*i<=c[ord[mid]]) r=mid-1;
else p=mid,l=mid+1;
} //printf("%d %d
",i,p);
chkmin(res,suma[n-i]+sumc[p]+1ll*(sumb[m]-sumb[p])*i);
} printf("%lld
",res);
return 0;
}