New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

1903: 修建花园

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：0 通过：0
提交提交记录统计

题目描述

Farmer John 打算修建一座花园，他需要移动不少泥土。
花园由 N 个花坛组成，其中花坛 i 包含 Ai 单位的泥土。
FJ 希望花坛 i 包含 Bi 单位的泥土。
为此他可以：
  • 购买一单位的泥土，放在指定的花坛中，费用为 X。
  • 从任意一个花坛中移走一单位泥土，费用为 Y。
  • 从花坛 i 运送一单位泥土到花坛 j，费用为 Z∣i−j∣。
请你帮 FJ 计算移动泥土的最小开销。

输入格式

第一行四个整数 N,X,Y,Z（1≤N≤100，0≤X,Y,Z≤1000）。
接下来 N 行，第 i 行两个整数 Ai,Bi，0≤Ai,Bi≤10。

输出格式

输出移动泥土的最小开销。

输入样例 复制 

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

输出样例 复制 

210

数据范围与提示

按下面的方案，最小花费为 210，可以证明不存在开销更小的方案。
  • 移除 4 号花坛的一单位泥土，花费 200。
  • 将 4 号花坛的三单位泥土移到 1 号花坛，花费 3×3=9。
  • 将 3 号花坛的一单位泥土移到 2 号花坛，花费 1×1=1。
来源：USACO 2012.3