# 题目分析

$$a(B+b)+a ‘ (B+b+b ‘ ) < a ' (B+b ' )+a(B+b+b ' )$$

$$Sa_{i+1}b_i+(Sb_i-1)a_i+Sa_{j+1}b_j+(Sb_j-1)a_j-a_jb_i$$

# 代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int q=0;char ch=' ';
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
return q;
}
typedef long long LL;
const int N=300005;
int n,ATK,flag[N<<2];LL ans,sum;
LL Sa[N],Sb[N],B[N<<2],K[N<<2];
struct node{int a,b;}d[N];

void insert(int s,int t,int i,LL k,LL b) {
if(!flag[i]) {K[i]=k,B[i]=b,flag[i]=1;return;}
int mid=(s+t)>>1;
LL l1=1LL*s*k+b,l2=1LL*s*K[i]+B[i],r1=1LL*t*k+b,r2=1LL*t*K[i]+B[i];
LL m1=1LL*mid*k+b,m2=1LL*mid*K[i]+B[i];
if(l1<=l2&&r1<=r2) return;
if(l1>l2&&r1>r2) {K[i]=k,B[i]=b;return;}
if(l1>l2) {
if(m1>m2) insert(mid+1,t,(i<<1)|1,K[i],B[i]),K[i]=k,B[i]=b;
else insert(s,mid,i<<1,k,b);
}
else {
if(m1>m2) insert(s,mid,i<<1,K[i],B[i]),K[i]=k,B[i]=b;
else insert(mid+1,t,(i<<1)|1,k,b);
}
}
LL query(int x,int s,int t,int i) {
if(s==t) return 1LL*x*K[i]+B[i];
int mid=(s+t)>>1;LL re=1LL*x*K[i]+B[i];
if(x<=mid) re=max(re,query(x,s,mid,i<<1));
else re=max(re,query(x,mid+1,t,(i<<1)|1));
return re;
}

int cmp(node x,node y) {return 1LL*y.a*x.b<1LL*x.a*y.b;}
LL getK(int x) {return -d[x].a;}
LL getB(int x) {return 1LL*Sa[x+1]*d[x].b+1LL*(Sb[x]-1)*d[x].a;}
int main()
{
sort(d+1,d+1+n,cmp);
for(RI i=n;i>=1;--i) Sa[i]=Sa[i+1]+d[i].a;
for(RI i=1;i<=n;++i) Sb[i]=Sb[i-1]+d[i].b;
for(RI i=1;i<=n;++i) sum+=1LL*d[i].a*(Sb[i]-1);
insert(1,10000,1,getK(n),getB(n)),ans=sum;
for(RI i=n-1;i>=1;--i) {
LL kl=query(d[i].b,1,10000,1);
ans=min(ans,sum-(getB(i)+kl));
insert(1,10000,1,getK(i),getB(i));
}
printf("%lld\n",ans);
return 0;
}