看这道题的时候，感觉很难，因为数据范围比较大，很难dp；
后来想到了【书柜的尺寸】这道题，也是一道dp，曾经看了那道题的题解而深有启发；
这道题每组的付费只与这一组长宽的最大值有关，也就是说要分组，一定从按长或宽的从大到小（从小到大也可以）排序，这样剔除无用的数据后，就只剩下一串数据，长从大到小，宽从小到大；
然后我们要在这里面分组，可以轻易发现，一个组的成员一定是连续的，原因与单调性有关；
这样就成了经典的dp，加上一个斜率优化即可轻松水过；
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int maxn=;
#define LL long long
int n,q[maxn];
struct node{
int x,y;
bool operator<(const node& c)const{return (x>c.x)||(x==c.x&&y>c.y);}
}a[maxn],b[maxn];
LL f[maxn];
double col(int j,int k){return double(f[k]-f[j])/double(b[j+].x-b[k+].x);}
void init(){
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
sort(a+,a+n+);int head=,tail=;
b[++tail]=a[];
for(int i=;i<=n;i++)if(a[i].y>b[tail].y)b[++tail]=a[i];
n=tail;
head=,tail=;q[++tail]=;
for(int i=;i<=n;i++){
while(head<tail&&col(q[head],q[head+])<=b[i].y)head++;
f[i]=f[q[head]]+(LL)b[q[head]+].x*b[i].y;
while(head<tail&&col(q[tail],i)<=col(q[tail],q[tail-]))tail--;
q[++tail]=i;
}
cout<<f[n]<<endl;
}
int main(){
init();
}