A2831. Landscaping P
编程题
提高+/省选-
知识点
题目描述
小李打算修建一座花园，他需要移动不少泥土。
花园由 $N$ 个花坛组成（$1 \leq N \leq 10^5$），其中花坛 $i$ 包含 $A_i$ 单位的泥土。小李 希望花坛 $i$ 包含 $B_i$ 单位的泥土，保证 $0 \leq A_i,B_i \leq 10$。
为了达到这个目标，他可以做这几件事情：
- 购买一单位的泥土，放在指定的花坛中，费用为 $X$。
- 从任意一个花坛中移走一单位泥土，费用为 $Y$。
- 从花坛 $i$ 运送一单位泥土到花坛 $j$，费用为 $Z|i-j|$。
请你帮小李计算移动泥土的最小开销。
花园由 $N$ 个花坛组成（$1 \leq N \leq 10^5$），其中花坛 $i$ 包含 $A_i$ 单位的泥土。小李 希望花坛 $i$ 包含 $B_i$ 单位的泥土，保证 $0 \leq A_i,B_i \leq 10$。
为了达到这个目标，他可以做这几件事情：
- 购买一单位的泥土，放在指定的花坛中，费用为 $X$。
- 从任意一个花坛中移走一单位泥土，费用为 $Y$。
- 从花坛 $i$ 运送一单位泥土到花坛 $j$，费用为 $Z|i-j|$。
请你帮小李计算移动泥土的最小开销。
输入格式
第一行四个整数 $N,X,Y,Z$（$0 \leq X,Y \leq 10^8$，$0 \leq Z \leq 1000$）。
接下来 $N$ 行，第 $i$ 行两个整数 $A_i,B_i$。
接下来 $N$ 行，第 $i$ 行两个整数 $A_i,B_i$。
输出格式
输出移动泥土的最小开销。
输入输出样例
输入 #1
4 100 200 1 1 4 2 3 3 2 4 0
输出 #1
210
说明/提示
按下面的方案，最小花费为 $210$，可以证明不存在开销更小的方案。
- 移除 $4$ 号花坛的一单位泥土，花费 $200$。
- 将 $4$ 号花坛的三单位泥土移到 $1$ 号花坛，花费 $3 \times 3=9$。
- 将 $3$ 号花坛的一单位泥土移到 $2$ 号花坛，花费 $1 \times 1=1$。
- 移除 $4$ 号花坛的一单位泥土，花费 $200$。
- 将 $4$ 号花坛的三单位泥土移到 $1$ 号花坛，花费 $3 \times 3=9$。
- 将 $3$ 号花坛的一单位泥土移到 $2$ 号花坛，花费 $1 \times 1=1$。