A22542.Landscaping P
提高+/省选-
USACO
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
小李打算修建一座花园,他需要移动不少泥土。
花园由 N 个花坛组成(1≤N≤105),其中花坛 i 包含 Ai 单位的泥土。小李 希望花坛 i 包含 Bi 单位的泥土,保证 0≤Ai,Bi≤10。
为了达到这个目标,他可以做这几件事情:
- 购买一单位的泥土,放在指定的花坛中,费用为 X。
- 从任意一个花坛中移走一单位泥土,费用为 Y。
- 从花坛 i 运送一单位泥土到花坛 j,费用为 Z∣i−j∣。
请你帮小李计算移动泥土的最小开销。
输入格式
第一行四个整数 N,X,Y,Z(0≤X,Y≤108,0≤Z≤1000)。
接下来 N 行,第 i 行两个整数 Ai,Bi。
输出格式
输出移动泥土的最小开销。
输入输出样例
输入#1
4 100 200 1 1 4 2 3 3 2 4 0
输出#1
210
说明/提示
按下面的方案,最小花费为 210,可以证明不存在开销更小的方案。
- 移除 4 号花坛的一单位泥土,花费 200。
- 将 4 号花坛的三单位泥土移到 1 号花坛,花费 3×3=9。
- 将 3 号花坛的一单位泥土移到 2 号花坛,花费 1×1=1。