[AdditionalFile2419.zip](file://AdditionalFile2419.zip?type=additional_file)

#2419. 「USACO 2016 US Open, Platinum」Landscaping

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 USACO 2016 US Open Contest, Platinum Problem 3. Landscaping

FJ 正修建一个漂亮的花园。花园由 $N$ 个花圃组成，花圃 $i$ 初始时有 $A_i$ 立方米的泥土。他想重建花园使得花圃 $i$ 有 $B_i$ 立方米的泥土。
他有几种操作方式：

1. 选择一个花圃，买一立方米泥土放进去，花费为 $x$；
2. 选择一个花圃，挖出并运走一立方米泥土，花费为 $y$；
3. 选择两个花圃 $i,j$，把一立方米泥土从 $i$ 运到 $j$，花费$z \times |i-j|$。

请求出完成重建的最小花费。

输入格式

第一行有四个整数 $N,x,y,z$。
在接下来的 $i$ 行中，第 $i$ 行有两个整数 $A_i,B_i$。

输出格式

输出最小重建花费。

样例

输入

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

输出

210

数据范围与提示

$1 \leq N \leq 10^5,$ $0 \leq A_i,B_i \leq 10,$ $0 \leq X, Y \le 10^8,$ $0 \le Z \leq 1000$。