自己推的式子：对于$k<j<i$

$L_i\geq \frac{f_j-f_k}{W_{k+1}-W_{j+1}}$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+5;
int n,idx;
struct node{
	int w,l;
}a[N],na[N];
bool cmp(node x,node y)
{
	return x.l==y.l?x.w<y.w:x.l<y.l;
}
int f[N];
int q[N],h=1,t=1;
double xl(int i,int j)
{
	return 1.0*(f[j]-f[i])/(na[i+1].w-na[j+1].w);
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&a[i].l,&a[i].w);
	sort(a+1,a+1+n,cmp);
	int l=1,r=1;
	while(l<=n && r<=n)
	{
		while(a[r+1].w>=a[l].w)
			r++;
		na[++idx]=a[r];
		l=++r;
	}
//	for(int i=1;i<=idx;i++)
//	{
//		printf("%lld %lld\n",na[i].l,na[i].w);
//	}
	q[1]=0;
	for(int i=1;i<=idx;i++)
	{
		while(h<t && xl(q[h],q[h+1])<=na[i].l)
			h++;
		f[i]=f[q[h]]+na[i].l*na[q[h]+1].w;
		while(h<t && xl(q[t-1],q[t])>=xl(q[t],i))
			t--;
		q[++t]=i;
	}
	printf("%lld",f[idx]);
	return 0;
}