记录编号	81686	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO NOV]金发姑娘和N头牛	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.079 s
提交时间	2013-11-16 19:47:02	内存使用	0.44 MiB

/*
ID:cstdio
PROG:milktemp
LANG:C++
*/
#include<iostream>
#include<cstdio>
#include<set>
#include<vector>
#include<cstring>
#include<deque>
#include<cstring>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
const int SIZEN=20001;
int A[SIZEN]={0},B[SIZEN]={0};
int N,X,Y,Z;
vector<int> tpt;
deque<int> lower;
deque<int> upper;
int calc(int x){
	int sum=0;
	sum+=lower[x]*Z;
	sum+=upper[x]*X;
	sum+=(N-lower[x]-upper[x])*Y;
	return sum;
}
void work(void){
	int ans=0;
	int i;
	for(i=0;i<lower.size();i++) ans=max(ans,calc(i));
	printf("%d\n",ans);
}
void getlower(int s[],deque<int> &f){//严格小于
	int i;
	int tot=0;
	for(i=0;i<tpt.size();i++){
		if(i>0&&tpt[i]==tpt[i-1]) continue;
		while(tot+1<=N&&s[tot+1]<tpt[i]) tot++;
		f.push_back(tot);
	}
}
void getupper(int s[],deque<int> &f){//严格大于
	int i;
	int tot=N+1;
	for(i=tpt.size()-1;i>=0;i--){
		if(i<tpt.size()-1&&tpt[i]==tpt[i+1]) continue;
		while(tot-1>=1&&s[tot-1]>tpt[i]) tot--;
		f.push_front(N+1-tot);
	}
}
bool gtr(int x,int y){
	return x>y;
}
void init(void){
	scanf("%d%d%d%d",&N,&X,&Y,&Z);
	int i;
	tpt.push_back(-1);
	tpt.push_back(0x7fffffff);
	for(i=1;i<=N;i++){
		scanf("%d%d",&A[i],&B[i]);
		tpt.push_back(A[i]);
		tpt.push_back(B[i]);
	}
	sort(tpt.begin(),tpt.end());
	sort(A+1,A+1+N);
	sort(B+1,B+1+N);
}
int main(){
	freopen("milktemp.in","r",stdin);
	freopen("milktemp.out","w",stdout);
	init();
	getlower(B,lower);
	getupper(A,upper);
	work();
	return 0;
}