Description

Farmer John plans to build a garden, and he needs to move a lot of soil.

The garden consists of $N$ flowerbeds ($1 \leq N \leq 10^5$). Flowerbed $i$ initially contains $A_i$ units of soil. FJ wants flowerbed $i$ to contain $B_i$ units of soil. It is guaranteed that $0 \leq A_i,B_i \leq 10$.

To achieve this, he can do the following:

• Buy one unit of soil and put it into a specified flowerbed, at a cost of $X$.
• Remove one unit of soil from any flowerbed, at a cost of $Y$.
• Transport one unit of soil from flowerbed $i$ to flowerbed $j$, at a cost of $Z|i-j|$.

Please help FJ compute the minimum cost to move the soil.

Input Format

The first line contains four integers $N,X,Y,Z$ ($0 \leq X,Y \leq 10^8$，$0 \leq Z \leq 1000$).

The next $N$ lines each contain two integers $A_i,B_i$ on line $i$.

Output Format

Output the minimum cost to move the soil.

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

210

Hint

Using the plan below, the minimum cost is $210$. It can be proven that no plan with a smaller cost exists.

• Remove one unit of soil from flowerbed $4$, costing $200$.
• Move three units of soil from flowerbed $4$ to flowerbed $1$, costing $3 \times 3=9$.
• Move one unit of soil from flowerbed $3$ to flowerbed $2$, costing $1 \times 1=1$.

Translated by ChatGPT 5