A22542.Landscaping P

提高+/省选-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小李打算修建一座花园,他需要移动不少泥土。

花园由 NN 个花坛组成(1N1051 \leq N \leq 10^5),其中花坛 ii 包含 AiA_i 单位的泥土。小李 希望花坛 ii 包含 BiB_i 单位的泥土,保证 0Ai,Bi100 \leq A_i,B_i \leq 10

为了达到这个目标,他可以做这几件事情:

  • 购买一单位的泥土,放在指定的花坛中,费用为 XX
  • 从任意一个花坛中移走一单位泥土,费用为 YY
  • 从花坛 ii 运送一单位泥土到花坛 jj,费用为 ZijZ|i-j|

请你帮小李计算移动泥土的最小开销。

输入格式

第一行四个整数 N,X,Y,ZN,X,Y,Z0X,Y1080 \leq X,Y \leq 10^80Z10000 \leq Z \leq 1000)。

接下来 NN 行,第 ii 行两个整数 Ai,BiA_i,B_i

输出格式

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

输入输出样例

  • 输入#1

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

    输出#1

    210

说明/提示

按下面的方案,最小花费为 210210,可以证明不存在开销更小的方案。

  • 移除 44 号花坛的一单位泥土,花费 200200
  • 44 号花坛的三单位泥土移到 11 号花坛,花费 3×3=93 \times 3=9
  • 33 号花坛的一单位泥土移到 22 号花坛,花费 1×1=11 \times 1=1
首页