记录编号	107537	评测结果	AAAAAAAAAAAAA
题目名称	[CEOI2004]锯木厂选址	最终得分	100
用户昵称	sbit	是否通过	通过
代码语言	C++	运行时间	0.026 s
提交时间	2014-06-27 18:37:40	内存使用	0.78 MiB

//{HEADS
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
#include <string>
#define REP(i,j) for(int i=1;i<=j;++i)
#define REPI(i,j,k) for(int i=j;i<=k;++i)
#define REPD(i,j) for(int i=j;0<i;--i)
#define STLR(i,con) for(int i=0,sz=con.size();i<sz;++i)
#define STLRD(i,con) for(int i=con.size()-1;0<=i;--i)
#define CLR(s) memset(s,0,sizeof s)
#define SET(s,v) memset(s,v,sizeof s)
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define PL(k,n) for(int i=1;i<=n;++i) { cout<<k[i]<<' '; } cout<<endl
#define PS(k) STLR(i,k) { cout<<k[i]<<' '; } cout<<endl
using namespace std;
typedef long long LL;
typedef double DB;
typedef pair<int,int> i_pair;
const int INF = 0x3f3f3f3f;
const long long INFL = 0x3f3f3f3f3f3f3f3f;
void read(int &a) {
	a=0;
	char c=getchar();
	int flag=0;
	while(c==' ' || c=='\n' || c=='\r') c=getchar();
	if(c=='-') {
		flag=1;
		c=getchar();
	}
	while('0'<=c && c<='9') {
		a=a*10+c-'0';
		c=getchar();
	}
	a=(flag==0?a:-a);
}
void read(LL &a) {
	a=0;
	char c=getchar();
	int flag=0;
	while(c==' ' || c=='\n' || c=='\r') c=getchar();
	if(c=='-') {
		flag=1;
		c=getchar();
	}
	while('0'<=c && c<='9') {
		a=a*10+c-'0';
		c=getchar();
	}
	a=(flag==0?a:-a);
}
void read(int &a,int &b) {
	read(a),read(b);
}
void read(int &a,int &b,int &c) {
	read(a),read(b),read(c);
}
void read(LL &a,LL &b) {
	read(a),read(b);
}
//}

const int maxn = 20000 + 100;

int n,w[maxn],d[maxn],sd[maxn],sw[maxn],q[maxn],cost[maxn],head,tail;

inline DB S(int a,int b) {
	return (DB)(sd[a]*sw[a]-sd[b]*sw[b])/(sw[a]-sw[b]);
}
inline int sec(int i,int j) {
	return cost[j]-cost[i-1]-sw[i-1]*(sd[j]-sd[i-1]);
}
inline int calc(int i,int j) {
	return cost[i]+sec(i+1,j)+sec(j+1,n+1);
}

int main() {
/*FILE{*/
#define FILE_IN_OUT
#ifdef FILE_IN_OUT
#ifndef ONLINE_JUDGE
	string FILE_NAME = "COGS362";
	FILE_NAME="two";
	freopen((FILE_NAME+".in").c_str(),"r",stdin);
	freopen((FILE_NAME+".out").c_str(),"w",stdout);
#endif
#endif/*}*/

	scanf("%d",&n);
	for(int i=1;i<=n;++i) {
		scanf("%d%d",&w[i],&d[i]);
	}
	for(int i=1;i<=n+1;++i) {
		sd[i+1]=sd[i]+d[i];
		sw[i]=sw[i-1]+w[i];
		cost[i+1]=cost[i]+d[i]*sw[i];
	}
	head=0,tail=-1;
	int ans=INF*2;
	for(int i=1;i<=n;++i) {
		while(head<tail && S(q[head],q[head+1])<=sd[i]) {
			++head;
		}
		ans=min(ans,calc(q[head],i));
		while(head<tail && S(q[tail-1],q[tail])>S(q[tail],i)) {
			--tail;
		}
		q[++tail]=i;
	}
	printf("%d\n",ans);

	return 0;
}