农 夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.

* 第1行: 一个数: N

* 第2..N+1行: 第i+1行包含两个数,分别为第i块土地的长和宽

* 第一行: 最小的可行费用.

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#define RG register
#define int long long
const int N = 100000;
const int inf = 2147483641;

using namespace std;

int gi(){
	char ch=getchar();int x=0;
	while(ch<‘0‘ || ch>‘9‘) ch=getchar();
	while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
	return x;
}

struct date{
	int a,b;
	bool operator < (const date c) const{
		if (a==c.a) return b>c.b;
		return a<c.a;
	}
}f[N];

int st[N],fa[N],dp[N],l=1,r=1,sa[N],t;

int find(int a){
	return a==fa[a]?a:fa[a]=find(fa[a]);
}

long double cal(int k,int y){
	if (f[find(k+1)].b==f[find(y+1)].b) return inf;
	return (long double)(dp[y]-dp[k])/(long double)(f[find(k+1)].b-f[find(y+1)].b);
}

main(){
	int n=gi();
	for (RG int i=1; i<=n; ++i) f[i]=(date){gi(),gi()},fa[i]=i;
	st[1]=fa[0]=0,sort(f+1,f+n+1);
	for (RG int i=1; i<=n; ++i){
		while(t && f[sa[t]].b<=f[i].b) fa[sa[t]]=i,--t;
		sa[++t]=i;
		while(l<r && cal(st[l],st[l+1])<=f[i].a) ++l;
		dp[i]=dp[st[l]]+f[i].a*f[find(st[l]+1)].b;
		while(l<r && cal(st[r-1],st[r])>=cal(st[r],i)) --r;
		st[++r]=i;
	}
	printf("%lld",dp[n]);
	return 0;
}