8586: BZOJ4586:[Usaco2016 Open]Landscaping

Memory Limit:128 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

农夫约翰正在建造一个美丽的花园,在这个过程中需要移动大量的泥土。花园由N个花圃(1≤N≤100,000)组成, 第i个花圃最开始有Ai个泥土。 农夫约翰想要重新整理花园,使每个花圃最后有Bi个泥土。Ai和Bi都是0...10范围 内的整数。为了整理花园,Farmer John有几个选择:他可以购买一个单位的泥土,并将它放在他选择的花圃中, 用X单位的钱。 他可以从他选择的花圃上清除一块泥土,并用Y单位的钱运出去。他还可以用Z*|i-j|的花费将一单 位的泥土从花圃i运输到花圃j。请计算农民约翰完成他的绿化项目的最低总成本。


输入格式

第一行输入包含N,X,Y和Z(0≤X,Y≤10^8; 0≤Z≤1000)。 行i + 1包含整数Ai和Bi。


输出格式

请输出FJ需要花在园林绿化上的最低总成本。


样例输入

4 100 200 1
1 4
2 3
3 2
4 0

样例输出

210

提示

没有写明提示


题目来源

Platinum 鸣谢g1n0st提供译文

加入题单

上一题 下一题 算法标签: